java - 最长的数字序列

Question

我最近在一次采访中被问到这个问题，我可以给出 O(nlogn) 解决方案，但找不到 O(n) 的逻辑。有人可以帮我解决 O(n) 问题吗？

在数组中找到最长数字序列的长度

示例: 输入:2 4 6 7 3 1 输出:4(因为 1,2,3,4 是一个序列，即使它们不在连续的位置)

该解决方案在占用空间方面也应该是现实的。即即使有 10 亿个数字的数组，解决方案也应该是现实的

Answer 1

对于非连续数字，您需要一种在 O(n) 中对它们进行排序的方法。在这种情况下，您可以使用 BitSet。

int[] ints = {2, 4, 6, 7, 3, 1};
BitSet bs = new BitSet();
IntStream.of(ints).forEach(bs::set); 

// you can search for the longer consecutive sequence.
int last = 0, max = 0;
do {
    int set = bs.nextSetBit(last);
    int clear = bs.nextClearBit(set + 1);
    int len = clear - set;
    if (len > max)
        max = len;
    last = clear;
} while (last > 0);
System.out.println(max);