algorithm - 用 O(nlogn) 时间解决问题

Question

设 A[1]<=A[2]<=....<=A[n]。令 X 为任意数。给出一个算法找到所有 A[i] 和 A[j] 对，使得 A[j] - A[i] >= X。所有数字都是正整数。

如果想看原题。在这里:

令 P = {p1; p2; ; pn} 是二维空间中的一组 n 个点，其中对于每个 i，pi = (xi; yi)。令 D = (dx; dy)。问题是确定是否存在一对点 pi 和 pj 使得 xj - xi >= dx 和 yj - yi >= dy。通过考虑所有可能的点对，您可以在 O(n^2) 时间内轻松解决此问题。但是我们有兴趣开发一个 O(n log n) 时间算法。

Answer 1

在这里，您可以利用输入已排序且所有数字均为正整数这一事实。如果

A[j] - A[i] ≥ X

那么我们知道下面的也是成立的

A[j + 1] - A[i] ≥ X

所以算法可能是

for(i = 1; i < n; i++) // for every value (this part is O(n))
{
    int minJ = A[i] + X; // the minimum J that satisfies `A[j] - A[i] >= X`

    int cutoff = binarySearch(minJ); // figure out the minimum J for which  `A[j] - A[i] >= X` (this part is O(log(n))

    storeResults(i, cutoff, n); // In Answers[i], save every qualifying integer (this part is less than O(log(n))
}

总共有

O(n * (log(n) + 小于 log(n))
O(n * (2 log(n)))
O(n * log(n))

还有一些小优化的余地，比如只将主循环执行到 n - 1 而不是 n，但这并不重要或与 Big-哦。