时间戳

首页 > 解决方案 > 给定一个包含 n 个点的数组，两点之间的距离定义为 min(abs(x1-x2), abs(y1-y2)) 。找到第 k 个最小距离

algorithm - 给定一个包含 n 个点的数组，两点之间的距离定义为 min(abs(x1-x2), abs(y1-y2)) 。找到第 k 个最小距离

问题描述

我已经使用最大优先级队列解决了这个问题。我所做的是通过迭代所有可能的对来不断插入距离，直到它的大小变为 k。然后，如果我发现当前距离大于 max-heap 顶部，我会弹出 max-heap 并插入这个距离。然后在迭代所有可能的对之后，最大堆顶部将是我们的答案。这个解决方案的时间复杂度似乎是 O(n^2 logn) 和空间复杂度 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();
}

标签： algorithmdata-structures

解决方案

这是一种更快的方法。快多少很难说，我的猜测可能是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))对数次搜索后，您会找到正确的。并且每次搜索本身都会尽可能地尝试以块为单位计算数字。（四叉树结构有帮助。）

祝你好运，使这个轮廓精确！

推荐阅读