找到它形成一个序列，最大的子集 [英] Find the largest subset of it which form a sequence

问题描述

我在接受采访时论坛遇到了这个问题。

I came across this problem during an interview forum.,

由于可能包含重复，找到它的形成序列中最大的子集的int数组。 例如。 {1,6,10,4,7,9,5} 那么ANS是4,5,6,7 排序是一个显而易见的解决方案。可以在O（n）的时间这样做。

Given an int array which might contain duplicates, find the largest subset of it which form a sequence. Eg. {1,6,10,4,7,9,5} then ans is 4,5,6,7 Sorting is an obvious solution. Can this be done in O(n) time.

我拿的问题是，这不能做O（n）的时间和放大器;其原因是，如果我们能在O（n）的时间做到这一点，我们可以做的O（n）时间还排序（不知道的上限）。 作为一个随机序列可包含序列的随机排序的所有元素。

My take on the problem is that this cannot be done O(n) time & the reason is that if we could do this in O(n) time we could do sorting in O(n) time also ( without knowing the upper bound). As a random array can contain all the elements in sequence but in random order.

这听起来一个合理的解释？你的看法。

Does this sound a plausible explanation ? your thoughts.

推荐答案

我相信它可以在O（n）的得到解决，如果你认为你有足够的内存来分配大小等于最大值的一个未初始化数组，该分配可以在一定的时间来完成。诀窍是使用一个懒惰的阵列，从而使您能够创建一组线性时间的项目与在固定时间内一个成员测试的能力。

I believe it can be solved in O(n) if you assume you have enough memory to allocate an uninitialized array of a size equal to the largest value, and that allocation can be done in constant time. The trick is to use a lazy array, which gives you the ability to create a set of items in linear time with a membership test in constant time.

第1阶段：经过每个项目，并把它添加到懒惰的阵列

Phase 1: Go through each item and add it to the lazy array.

第2阶段：穿过每个未删除的项目，并删除所有相邻的项目

Phase 2: Go through each undeleted item, and delete all contiguous items.

在第二阶段，确定了范围，并记住它，如果它是迄今为止规模最大的。项目可以在固定时间使用双链表中删除。

In phase 2, you determine the range and remember it if it is the largest so far. Items can be deleted in constant time using a doubly-linked list.

下面是一些令人难以置信的缺憾code演示的想法：

Here is some incredibly kludgy code that demonstrates the idea:

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);
}

这篇关于找到它形成一个序列，最大的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！