高效查找高密度区间的最佳数据结构

Question

我有一组未排序的整数和一个区间长度。我需要找到给定区间中包含的元素的最大子集

示例1:

Set: [11, 1, 2, 100, 12, 14, 99]
Interval: 4
Result: [11, 12, 14]

示例2:

Set: [1, 100, 55, 2, 88, 3]
Interval: 10
Result: [1, 2, 3]

在实践中，集合中有更多的元素

解决这个问题的有效数据结构和算法是什么？

Answer 1

1. 将整数集排序为数组A，并使w为区间的宽度。

2. 初始化i = j = best_start = best_n = 0。

3. 将j增加到A[j] < A[i] + w(或<=，具体取决于定义间隔的方式(。

4. 如果j - i > best_n设置best_start = i和best_n = j - i。

5. 递增i = i + 1，如果i, j < length(A)返回2。

总复杂度由初始排序复杂度O(n log n(决定。排序后注意到复杂性必须是线性的，因为j < n只能增加，并且我们在每一步都要做恒定数量的东西。

Answer 2

您应该首先对数组进行排序(O(N(*log(N((，然后从开始遍历数组，保持间隔。如果当前数字超过间隔，则存储该数组。如果发现较大的子集，则可以更新存储。

该算法的时间复杂度将是O(N(*log(N(+O(N。空间复杂度为O(N(。