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

Answer 2

遍历数组一次并构建哈希映射，其键是输入数组中的一个数字，值是一个布尔变量，指示元素是否已被处理（最初都是假的）。再次遍历并执行以下操作：当您检查 number 时a，将该元素的值放入哈希映射中，并立即检查哈希映射是否存在元素a-1和a+1。如果找到，将它们在哈希图中的值表示为真，并继续检查它们的邻居，增加当前连续子序列的长度。当没有邻居时停止，并更新最长的长度。在数组中向前移动并继续检查未处理的元素。乍一看，这个解决方案并不明显O(n)，但是只有两次数组遍历，并且哈希映射确保输入的每个元素只处理一次。

主要课程 - 如果您必须降低时间复杂度，通常需要使用额外的空间。