Блог

Я столкнулся с этой проблемой во время интервью на форуме.,

Учитывая массив int, который может содержать дубликаты, найдите его наибольшее подмножество, которое образует последовательность. Например. {1,6,10,4,7,9,5} тогда значение равно 4,5,6,7 Сортировка является очевидным решением. Можно ли это сделать за O (n) время.

Я считаю, что проблема заключается в том, что это невозможно сделать O (n) раз, и причина в том, что если бы мы могли сделать это за O (n) раз, мы могли бы выполнить сортировку также за O (n) раз (не зная верхней границы). Поскольку случайный массив может содержать все элементы последовательно, но в случайном порядке.

Звучит ли это правдоподобное объяснение? ваши мысли.

Я считаю, что это можно решить за O (n), если вы предполагаете, что у вас достаточно памяти для выделения неинициализированного массива размером, равным наибольшему значению, и это выделение может выполняться за постоянное время. Хитрость заключается в использовании отложенного массива, который дает вам возможность создавать набор элементов за линейное время с проверкой принадлежности за постоянное время.

Этап 1: просмотрите каждый элемент и добавьте его в отложенный массив.

Фаза 2: просмотрите каждый восстановленный элемент и удалите все смежные элементы.

На этапе 2 вы определяете диапазон и запоминаете его, если он пока самый большой. Элементы могут быть удалены за постоянное время с помощью двусвязного списка.

Вот какой-то невероятно запутанный код, который демонстрирует идею:

 int main(int argc,char **argv)
{
  static const int n = 8;
  int values[n] = {1,6,10,4,7,9,5,5};
  int index[n];
  int lists[n];
  int prev[n];
  int next_existing[n]; // 
  int prev_existing[n];
  int index_size = 0;
  int n_lists = 0;

  // Find largest value
  int max_value = 0;
  for (int i=0; i!=n;   i) {
    int v=values[i];
    if (v>max_value) max_value=v;
  }

  // Allocate a lazy array
  int *lazy = (int *)malloc((max_value 1)*sizeof(int));

  // Set items in the lazy array and build the lists of indices for
  // items with a particular value.
  for (int i=0; i!=n;   i) {
    next_existing[i] = i 1;
    prev_existing[i] = i-1;
    int v = values[i];
    int l = lazy[v];
    if (l>=0 amp;amp; l<index_size amp;amp; index[l]==v) {
      // already there, add it to the list
      prev[n_lists] = lists[l];
      lists[l] = n_lists  ;
    }
    else {
      // not there -- create a new list
      l = index_size;
      lazy[v] = l;
      index[l] = v;
        index_size;
      prev[n_lists] = -1;
      lists[l] = n_lists  ;
    }
  }
  // Go through each contiguous range of values and delete them, determining
  // what the range is.
  int max_count = 0;
  int max_begin = -1;
  int max_end = -1;
  int i = 0;
  while (i<n) {
    // Start by searching backwards for a value that isn't in the lazy array
    int dir = -1;
    int v_mid = values[i];
    int v = v_mid;
    int begin = -1;
    for (;;) {
      int l = lazy[v];
      if (l<0 || l>=index_size || index[l]!=v) {
        // Value not in the lazy array
        if (dir==1) {
          // Hit the end
          if (v-begin>max_count) {
            max_count = v-begin;
            max_begin = begin;
            max_end = v;
          }
          break;
        }
        // Hit the beginning
        begin = v 1;
        dir = 1;
        v = v_mid 1;
      }
      else {
        // Remove all the items with value v
        int k = lists[l];
        while (k>=0) {
          if (k!=i) {
            next_existing[prev_existing[l]] = next_existing[l];
            prev_existing[next_existing[l]] = prev_existing[l];
          }
          k = prev[k];
        }

        v  = dir;
      }
    }
    // Go to the next existing item
    i = next_existing[i];
  }

  // Print the largest range
  for (int i=max_begin; i!=max_end;   i) {
    if (i!=max_begin) fprintf(stderr,",");
    fprintf(stderr,"%d",i);
  }
  fprintf(stderr,"n");

  free(lazy);
}
  

Я бы сказал, что есть способы сделать это. Алгоритм — это тот, который вы уже описали, но просто используйте алгоритм сортировки O (n). Поскольку таковые существуют для определенных входных данных (сортировка по корзинам, сортировка по основаниям), это работает (это также идет рука об руку с вашей аргументацией, почему это не должно работать).

Вон Катон предложил реализацию, которая работает следующим образом (она работает как сортировка по корзинам, а отложенный массив работает как корзины по требованию).

Как показано М. Беном -Или в нижних границах для деревьев алгебраических вычислений, Proc. 15th ACM Sympos. Теория вычислений, стр. 80-86. 1983 цитируется J. Erickson в pdf Поиск самых длинных арифметических прогрессий, эта проблема не может быть решена менее чем за O (n log n) время (даже если входные данные уже отсортированы по порядку) при использовании алгебраической модели вычисления дерева решений.

Ранее я опубликовал следующий пример в комментарии, чтобы проиллюстрировать, что сортировка чисел не дает простого ответа на вопрос: предположим, что массив уже отсортирован в порядке возрастания. Например, пусть это будет (20 30 35 40 47 60 70 80 85 95 100). Самая длинная последовательность, найденная в любой подпоследовательности входных данных, равна 20,40,60,80,100, а не 30,35,40 или 60,70,80.

Относительно того, обеспечит ли решение этой проблемы с помощью O (n) алгебраического дерева решений метод сортировки O (n) алгебраического дерева решений: Как указывали другие, решение этой проблемы подпоследовательности для данного мультимножества не дает решения проблемы сортировки для этого мультимножества. В качестве примера рассмотрим множество {2,4,6, x, y, z}. Решатель подпоследовательности выдаст вам результат (2,4,6) всякий раз, когда x, y, z являются большими числами не в арифметической последовательности, и он ничего не скажет вам о порядке x, y, z .

Как насчет этого? заполните хэш-таблицу так, чтобы каждое значение сохраняло начало диапазона, видимого до сих пор для этого числа, за исключением элемента head, который хранит конец диапазона. O (n) время, O (n) пространство. Предварительная реализация Python (вы могли бы сделать это с помощью одного обхода, сохраняя некоторые переменные состояния, но этот способ кажется более понятным):

 def longest_subset(xs):
    table = {}
    for x in xs:
        start = table.get(x-1, x) 
        end = table.get(x 1, x)
        if x 1 in table:
            table[end] = start
        if x-1 in table:
            table[start] = end
        table[x] = (start if x-1 in table else end)

    start, end = max(table.items(), key=lambda pair: pair[1]-pair[0])
    return list(range(start, end 1))

print(longest_subset([1, 6, 10, 4, 7, 9, 5])) 
# [4, 5, 6, 7]
  

вот неоптимизированная реализация O (n), возможно, она вам пригодится:

 hash_tb={}
A=[1,6,10,4,7,9,5]

for i in range(0,len(A)):
    if not hash_tb.has_key(A[i]):
        hash_tb[A[i]]=A[i]
max_sq=[];cur_seq=[]
for i in range(0,max(A)):
    if hash_tb.has_key(i):
        cur_seq.append(i)
    else:
        if len(cur_seq)>len(max_sq):
            max_sq=cur_seq
        cur_seq=[]
print max_sq