arrays - 查找未排序数组中的所有对

Question

我在 find 中遇到了一个编程问题，我必须在给定的未排序数组中找到所有对，这样

|i - j| <= K and |A[i] - A[j]| <= x 

For example:

 A = {5,4,8,3} and x = 3 and k = 2.

答案:(5,4), (5,8), (4,3)

我已经尝试过很多次了，但是想不出任何时间复杂度小于O(nk) 的算法。我也尝试过平衡二叉树，但它对我没有帮助。

编辑:如果我们必须找到这样的对是否存在于数组中(这意味着只有一个这样的对)，我们能做点好事吗？

Answer 1

取前 N-1 个条目，并对它们进行排序。这给了你最小/最大和前几对。然后对于列表中的每个后续条目，它是根据最小值/最大值匹配部分、全部还是不匹配？如果它不匹配或全部匹配，则您将直接配对。如果它匹配一些，则进行二进制搜索以找到截止点。然后删除第一个条目并添加新条目，使用平衡二叉树来保存排序列表。

所以你是 O(N log k)。在实践中，开销会如此之高，以至于不太可能击败朴素的 O(Nk) 方法。