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

Question

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

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

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

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

Answer 1

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

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

Фаза 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 && l<index_size && 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);
}

Answer 2

Как показано М. Бен-Ором в Нижние оценки для деревьев алгебраических вычислений , Proc. 15-й симпозиум ACM. Теория вычислений. С. 80-86. 1983, цитируется Дж. Эриксоном в 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.

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

Answer 3

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

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

Answer 4

Вот неоптимизированная реализация 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

Answer 5

А как насчет этого?заполнить хеш-таблицу, чтобы каждое значение сохраняло начало диапазона, видимого на данный момент для этого числа, за исключением элемента 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]