algorithm - 找到构成序列的最大子集

Question

我在一个面试论坛上遇到了这个问题。，

给定一个可能包含重复项的 int 数组，找出其中构成序列的最大子集。 例如。 {1,6,10,4,7,9,5} 那么 ans 是 4,5,6,7 排序是一个显而易见的解决方案。这能在 O(n) 时间内完成吗？

我对这个问题的看法是，这不能在 O(n) 时间内完成，原因是如果我们可以在 O(n) 时间内完成，我们也可以在 O(n) 时间内完成排序(不知道上限)。 由于随机数组可以按顺序包含所有元素，但顺序是随机的。

这听起来合理吗？你的想法。

Answer 1

我相信它可以在 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 && 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);
}