给定n个点的数组，两点之间的距离定义为min(abs(x1-x2)，abs(y1-y2))。求第k个最小距离

Question

我已经用最大优先级队列解决了这个问题。我所做的是通过迭代所有可能的对来不断插入距离，直到它的大小变为k，然后如果我发现当前的距离大于max-heap top，我弹出max-heap并插入这个距离。然后，在迭代所有可能的对之后，max-heap top将是我们的答案。该方法的时间复杂度为O(n^2logn)，空间复杂度为O(k)。但我需要做得比这更好？还有什么其他的方法呢？

以下是代码快照：

int kthMin(vector<pair<int,int>> Points, int k) {
    priority_queue pq;

    for(int i=0;i<Points.size()-1; i++) {
        for(int j=i+1; j<Points.size(); j++) {
          int dist = min( abs(Points[i].first - Points[j].first), abs(Points[i].second - Points[j].second));
        if(pq.size()<k) pq.push(dist);
        else if(dist< pq.top()) {
          pq.pop();
          pq.push(dist);
        }
      }
    }
    return pq.top();
}

Answer 1

这里有一个更快的方法。很难说有多快，我猜可能是像O(n^(3/2) log(n))这样的。

首先，将所有的点放入一个四叉树中。让四叉树中的每个节点包含矩形中的点数以及x和y的最小和最大值作为元信息。

现在你的逻辑看起来像这样。

lower = 0
upper = max(tree.max_x - tree.min_x, tree.max_y - tree.min_y)
while lower < upper:
    mid = (lower + upper) / 2
    max_below = lower
    min_above = upper
    count_below = 0
    count_at = 0
    stack = new stack
    stack.push((tree, tree)) # To order them, 
    while stack is not empty:
        # We want ordered "pairs of points of interest" meaning
        # p1 in tree1, p2 in tree2 and either p1.x < p2.x
        # or p1.x = p2.x and p1.y <= p2.y.
        (tree1, tree2) = stack.pop()
        if no pairs of points of interest (eg tree2.max_x < tree1.min_x):
            pass
        elsif all of tree1 within distance mid of all of tree2:
            count_below += tree1.count * tree2.count
            if max_below < max possible distance from tree1 to tree2:
                max_below = max possible distance from tree1 to tree2
        elsif all of tree1 at distance mid of all of tree2:
            count_at += tree1.count * tree2.count
        elsif all of tree1 more than distance mid of all of tree2:
            if min possible distance from tree1 to tree2 < min_above:
                min_above = min possible distance from tree1 to tree2
        elsif longest axis of tree1 longer than longest axis of tree2:
            for child of tree1:
                stack.push((child, tree2))
        else:
            for child of tree2:
                stack.push((tree1, child))

    if k < count_below:
        upper = max_below
    elsif k <= count_below + count_at:
        return mid
    else:
        lower = min_above

这个想法是你的二进制搜索“捕捉”到O(n^2)可能的距离之一。所以在O(log(n))对数次搜索之后，你就会找到正确的答案。每次搜索本身都会尽可能地对块中的数字进行计数。(四叉树结构对此很有帮助。)

祝你好运，让这个大纲更精确！