Блог

Я видел следующий вопрос, хотя мне удалось решить его в O (n ^ 2), я думаю, мы можем добиться большего.

Заданный вектор целых чисел возвращает максимальное количество несмежных копий аналогичного числа.

Например, дано: [9,2,3,4,0,4,5,6,0,8]

мы видим, что у нас есть 2 несмежных 0 и 2 несмежных 4 (остальные — единицы), поэтому ответ max (2,2) = 2;

дано: [4,4,4,4,4]

у нас есть 3 несмежных 4, поэтому ответ равен 3. мы берем сначала 4, затем мы не можем взять соседний с ним (они соседние), поэтому мы берем следующий и так далее.

Мое решение: выполните итерацию по вектору и проверьте, сколько несмежных копий мы видим из текущего числа, если оно больше текущего максимума, мы соответствующим образом обновляем max.

Вопрос: Как мы можем решить это более эффективно?

Если вас устраивает использование O (n) пространства, вы можете использовать сегменты для значений, которые вы видите, для достижения O (n) времени выполнения.

Самый простой способ реализовать это с помощью map. ie:

 std::pair<int, int> max_adj(std::vector<int> arr) {
    std::map<int, int> buckets;
    
    for(int x = 0; x < arr.size(); x  ) {
        // Loop to eat up adjacent values
        int in_a_row = 1;
        for(int curr = x  ;
            x < arr.size() amp;amp; arr[curr] == arr[x];
            x  , in_a_row  ) { }
        x--; // The loop will increment x one past last dupe, so go back
        
        // Only count every other adjacent value seen
        buckets[arr[x]]  = (in_a_row   1) / 2;
    }
    
    // Find the most seen
    std::map<int, int>::iterator mx = std::max_element
    (
        buckets.begin(), buckets.end(),
        [] (const std::pair<int, int> amp;p1, const std::pair<int, int> amp;p2) {
            return p1.second < p2.second;
        }
    );
    
    if(mx != buckets.end()) {
        return *mx;
    }
    return std::pair<int, int>(-1, -1);
}
 

Живой пример: https://ideone.com/v9OOIA

Эта проблема может быть решена путем создания массива, который содержит число и его индекс, как показано ниже,

исходный массив = [9, 2, 3, 4, 0, 4, 5, 6, 0, 8] ,
числовой индексный массив = [ 9 , 0], [ 2 , 1], [ 3 , 2], [ 4 , 3], [ 0 , 4], [ 4 , 5], [ 5 , 6], [ 6 , 7], [ 0 , 8], [ 8 , 9]

Здесь первый элемент std::pair — это само число, а второй элемент — индекс числа.
После этого отсортируйте этот массив по числам, и результат будет следующим,
[ 0 , 8], [ 0 , 4], [ 2 , 1], [ 3 , 2], [ 4 , 5], [ 4 , 3],[ 5 , 6], [ 6 , 7], [ 8 , 9], [ 9 , 0]

Цель сортировки — привести одинаковые числа рядом друг с другом. Как только одинаковые числа оказываются смежными, для поиска ответа требуется простая итерация. Давайте посмотрим, как это работает,

Первое число в отсортированном массиве 0 и при нахождении upper bound 0 даст все смежные 0 , это означает, что будут доступны следующие,
[ 0 , 8], [ 0 , 4]
Но, как вы можете видеть выше, эти записи расположены не в порядке индекса, запись индекса 4 следует за записью индекса 8 , и это потому std::sort , что не являетсястабильная сортировка, это означает, что относительный порядок элементов не сохраняется. Поэтому, прежде чем продолжить, эти элементы должны быть снова отсортированы по индексу, и результат будет

[ 0 , 4], [ 0 , 8]
, Как показано выше, индексируют 4 и 8 не являются смежными 4 1 != 8 , а количество несмежных чисел равно two .

Все записи 0 проверяются, и алгоритм будет рассматривать следующее число, которое есть 2 , но, как вы видите выше, в массиве есть только одна запись числа, 2 которая есть [2, 1] , и из-за этого будет рассмотрен следующий номер, то же самое произойдет для всех чисел, поэтому давайте напрямую посмотрим на число 4 , и оно имеет более одной записи в качествепоказано ниже,
[ 4 , 5], [ 4 , 3]
затем отсортируйте эти записи по индексу,

[ 4 , 3], [ 4 , 5]
здесь снова индексы не являются смежными индексами 3 1 != 5 , а количество не смежных чисел равно two . Тот же процесс будет применен ко всем числам, и окончательный ответ будет максимальным не смежным числом count = 2

Для другого примера массива [4, 4, 4, 4, 4] конечное число и индексный массив этого будут,

[ 4 , 0], [ 4 , 1], [ 4 , 2], [ 4 , 3], [ 4 , 4]
И, как вы можете видеть, индекс 0 , 2 , 4 не являются смежными индексами и максимальным несмежным числом count = 3

 #include <iostream>

#include <vector>
#include <algorithm>

using std::cout;

std::size_t countNonAdjacentEntries(std::vector<std::pair<int, std::size_t>>::const_iterator firstIt,
                                    std::vector<std::pair<int, std::size_t>>::const_iterator lastIt){


    std::size_t count = 0;

    for(std::vector<std::pair<int, std::size_t>>::const_iterator preIt = firstIt, it = preIt   1; lastIt != it;){

        if(preIt->second   1 != it->second){

              count;

            preIt = it;
              it;
        }
        else{
              it;
        }
    }

      count;
    return count;
}

std::size_t maxNonAdjacentNumber(const std::vector<int>amp; numbers){

    std::vector<std::pair<int, std::size_t>> numAndIndex;
    numAndIndex.reserve(numbers.size());

    for(std::vector<int>::size_type i = 0, numbersCount = numbers.size(); i < numbersCount;   i){

        numAndIndex.emplace_back(numbers[i], i);
    }

    std::sort(numAndIndex.begin(), numAndIndex.end(),
              [](const std::pair<int, std::size_t>amp; a, const std::pair<int, std::size_t>amp; b){
        return a.first < b.first;});

    std::size_t count = 0;

    for(std::vector<std::pair<int, std::size_t>>::const_iterator it = numAndIndex.cbegin(), endIt = numAndIndex.cend();
        endIt != it; ){

        std::vector<std::pair<int, std::size_t>>::const_iterator upBoundIt = std::upper_bound( it   1, endIt, it->first,
                    [](int val, const std::pair<int, std::size_t>amp; ele){return val < ele.first;});

        if(upBoundIt - it > 1){

            std::sort(numAndIndex.begin(), numAndIndex.end(),
                      [](const std::pair<int, std::size_t>amp; a, const std::pair<int, std::size_t>amp; b){
                return a.second < b.second;});

            count = std::max(count, countNonAdjacentEntries(it, upBoundIt));
            it = upBoundIt;
        }
        else{
              it;
        }
    }

    return count;
}

int main(){

    cout<< "[9, 2, 3, 4, 0, 4, 5, 6, 0, 8] => "<< maxNonAdjacentNumber({9, 2, 3, 4, 0, 4, 5, 6, 0, 8})<< 'n';
    cout<< "[4, 4, 4, 4, 4] => "<< maxNonAdjacentNumber({4, 4, 4, 4, 4})<< 'n';
}

 

Вывод

 [9, 2, 3, 4, 0, 4, 5, 6, 0, 8] => 2
[4, 4, 4, 4, 4] => 3
 

уникальный, чтобы удалить дубликаты, отсортировать оставшиеся скопления, затем найти самый длинный прогон.

 template<class T, class A>
std::optional<T> most_runs_of( std::vector<T, A> r ) {
  if (r.empty()) return std::nullopt;
  r.erase( std::unique( begin(r), end(r) ), end(r) );
  std::sort( begin(r), end(r) );
  T winner = r.front();
  std::size_t winner_count = 0;
  T const* cur = nullptr;
  std::size_t cur_count = 0;
  for (T constamp; e:r) {
    if (e == winner)
    {
        winner_count;
      continue;
    }
    if (cur amp;amp; *cur==e) {
        cur_count;
      if (cur_count > winner_count) {
        winner = e;
        winner_count = cur_count;
        cur = nullptr;
        continue;
      }
    }
    cur = std::addressof(e);
    cur_count = 1;
  }
  return winner;
}
 

Это копирует std::vector и делает это на месте в копии в O (nlgn) и O (n) пространстве.

Если вам не нужно std::vector после того, как вы вызовете вышеуказанное, std::move включите его в алгоритм.