搜索彼此之间的差异小于固定值的数字的算法？

Question

假设存在一个巨大的真实数据集:A1,A2,A3,...,Ai,...An(其中 n 是一个非常大的数。)。我想找到这些子数据集，其中这些子集中每个数字之间的差异小于一个固定值 B。它必须花费尽可能少的时间和内存。有什么想法吗？

Answer 1

如评论中所述，集合已经排序。让我们称第 i 个元素为 a[i]。一个简单的线性传递找到所有子集(伪代码，不检查数据的结尾 - 这很容易添加，但会模糊算法的思想):

low = 0;
high = 0;
repeat {
    while (a[high] - a[low] <= B) {
        high = high + 1;
    }
    output set a[low .. high-1];
    while (a[high] - a[low] > B) {
        low = low + 1;
    }
}

请注意，一次只有 low 和 high 之间的部分需要在内存中。因此可以流式传输数据而无需将其全部存储在内存中。

这个算法也会输出一个元素子集。如果不需要，可以很容易地抑制它。