找到其中最大的子集，使其形成一个序列。

Question

找到其中最大的子集，使其形成一个序列。

algorithmtime-complexity

3

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

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

我的看法是这不能在O(n)的时间内完成，原因是如果我们能在O(n)的时间内完成这个问题，那么我们也可以在O(n)的时间内完成排序（不知道上限的情况下）。因为随机数组中可能包含所有元素的顺序但是是随机的。

你认为这个解释听起来可行吗？请分享你的想法。

- vindyz

无法想到任何可能以O(n)时间实际完成它的解决方案... - Varun

4

在实际编程中，你通常会知道整数的上限。因此，如果有足够的内存，你可以使用桶排序。但是对于任意整数（数学整数），你是正确的。 - arne

无法想象并不意味着不可能。 - j_kubik

找到上限也是O(n)，因此将其与桶排序结合使用可以得到O(n) - 因此在理论上是可能的（但对于大多数应用程序来说非常不切实际）。 - j_kubik

使用Scala编写和测试：https://github.com/sauravsahu02/practice-scala/blob/master/src/main/scala/google/problems/FindLargestSubset.scala - Saurav Sahu

显示剩余11条评论

5个回答

1

我认为有方法可以做到。算法就是你已经描述的那个，但只需使用O(n)排序算法。对于某些输入（桶排序、基数排序），这样做是可行的（这也与你的论证为什么它不起作用相吻合）。

Vaughn Cato建议的实现方式是这样的（它的工作方式类似于带有惰性数组的桶排序）。

- flolo

O(n)排序只有在您对输入进行假设时才能正常工作。由于没有提到这样的假设，因此这可能不起作用（除非，作为面试问题，正确答案是“我可以对输入做出什么假设”）。 - LiKao

1

正如M. Ben-Or在代数计算树的下限中所示，Proc. 15th ACM Sympos. Theory Comput.，pp. 80-86。1983年由J. Erickson在pdf Finding Longest Arithmetic Progressions引用，使用代数决策树模型计算时，即使输入已经按顺序排序，也不能在少于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}。子序列求解器将在x、y、z是不在算术序列中的大数时给出结果(2,4,6)，它不会告诉你x、y、z的顺序。

- James Waldby - jwpat7

0

这里有一个未经优化的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

- trailblazer

0

这个怎么样？使用哈希表填充，使每个值存储到目前为止该数字所见范围的开始，除了存储范围结束的头元素。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]

- tokland

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vaughn Cato · Accepted Answer

如果您假设有足够的内存来分配一个未初始化数组，其大小等于最大值，并且该分配可以在恒定时间内完成，那么我相信它可以在O(n)中解决。技巧是使用惰性数组，这使您能够在线性时间内创建具有常量时间成员资格测试的项目集。

第一阶段：遍历每个项目并将其添加到惰性数组中。

第二阶段：遍历每个未删除的项目，并删除所有连续的项目。

在第二阶段中，您确定范围并记住它（如果它是迄今为止最大的）。可以使用双向链表在常数时间内删除项目。

以下是演示该想法的一些极其混乱的代码：

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