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

Question

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

Answer 1

目前还不清楚你指的是多少数据--它是否小到足以将所有数据加载到内存中，是否为32位整数，数据中是否存在重复数据，是否使用多台机器和/或使用地图--减少作业等等。尽管缺乏信息，但我可以盲目地建议您使用基类。它的线性时间排序算法。

编辑1

正如您所提到的，数据已经按升序排序，因此我们可以使用二进制搜索(上限)来查找每个元素的所有子集。

假设数据容器是A[i]和n大小，下面是粗略的伪代码：

upper_bound(start, end, key):
    indx := end + 1
    while start <= end do
        mid := start + (end - start) / 2
        if A[mid] >= key:
            indx := mid
            end := mid - 1
        else
            start := mid + 1

     return indx
end


subsets := [] // list of subsets
for i = n - 1 to i = 0 do
    indx := upper_bound(0, i - 1, A[i] - B)
    set := [ elements from A[indx] to A[i] ]
    subsets.push(set)
end

print subsets

对于每个元素arr[i]，您必须找到上界；总的时间复杂度是O(n logn)。

如果您愿意，我可以提供C++或Java工作片段。

编辑2

以下是Java代码

import java.util.ArrayList;
import java.util.Arrays;

/**
 *
 * @author kaidul
 */
public class Test {

    private static int upperBound(int left, int right, int key, Integer[] A) {
        int indx = right + 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(A[mid] > key) {
                indx = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return indx;
    }

    public static void main(String[] args) {
        Integer[] A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int B = 4;
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for(int i = A.length - 1; i > 0; --i) {
            int startIndx = upperBound(0, i - 1, Math.min(A[i] - B, A[i] - A[0]), A);
            if(startIndx < i) {
                ArrayList<Integer> solutionSet = new ArrayList<>( Arrays.asList( Arrays.copyOfRange(A, startIndx, i + 1) ) );
                result.add(solutionSet);
            }
            if(startIndx == 0) {
                break;
            }
        }
        result.stream().forEach((subset) -> {
            System.out.println(subset);
        });
    }

}

输出：

[7, 8, 9, 10]
[6, 7, 8, 9]
[5, 6, 7, 8]
[4, 5, 6, 7]
[3, 4, 5, 6]
[2, 3, 4, 5]
[1, 2, 3, 4]

Answer 2

正如注释中提到的，集合已经排序。让我们调用i-th元素ai。简单的线性传递可以找到所有子集(伪代码，无需检查数据的结尾--这很容易添加，但会模糊算法的思想)：

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之间的部分一次需要在内存中。因此，可以在不将其全部存储在内存中的情况下通过数据流。

该算法还将输出一个元素子集。如果这是不想要的，它可以很容易地被抑制。