最长的子阵列,其元素形成连续序列

Question

给定未排序的正整数数组,找到最长子数组的长度,其中排序的元素是连续的.你能想到O(n)解决方案吗？

例:

{10,5,3,1,4,2,8,7},答案是5.

{4,5,1,5,7,6,8,4,1},答案是5.

对于第一个例子,子阵列{5,3,1,4,2}在排序时可以形成连续序列1,2,3,4,5,它们是最长的.

对于第二个例子,子阵列{5,7,6,8,4}是结果子阵列.

我可以想到一个方法,对于每个子阵列,检查(最大 - 最小+ 1)是否等于该子阵列的长度,如果为真,那么它是一个连续的子阵列.花费最长的.但它是O(n ^ 2)并且不能处理重复.

有人可以提供更好的方法吗？

Answer 1

以下是 3 个可接受的解决方案：

第一个是O(nlog(n))时间和O(n)空间，第二个是O(n)时间和O(n)空间，第三个是O(n)时间和O(1)空间。

1. 构建一个然后按顺序binary search tree遍历它。 保留 2 个指针，一个用于最大子集的开始，一个用于结束。迭代树时保留该值。这是时间和空间的复杂性。
   max_sizeO(n*log(n))

2. 您始终可以在线性时间内使用计数排序对数字集进行排序并遍历数组，这意味着O(n)时间和空间复杂度。

3. 假设没有溢出或大整数数据类型。假设数组是一个数学集合（没有重复值）。您可以在O(1)内存中执行此操作：

   • 计算数组的和以及数组的乘积
   • 假设你有原始集合的最小值和最大值，找出其中有哪些数字。总而言之就是O(n)时间复杂度。