algorithm - 有效找到高密度区间的最佳数据结构

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只能增加，并且我们在每一步都会做恒定数量的事情。