使用优先队列找到离原点最近的K个点

在这个问题中，我们将从给定的 N 个点中找到 2D 平面中距离原点最近的 K 个点。

我们可以使用标准的欧氏距离公式来计算原点到每个给定点之间的距离。之后，我们可以将有距离的点存储到数组中，根据距离对数组进行排序，并取前K个点。

然而，我们还可以使用优先队列根据点与原点的距离来存储二维点。之后，我们可以从队列中出队K次。

问题陈述− 我们在二维平面上给定了N个点。我们需要找到离平面原点最近的K个点。

注意- 将欧几里得距离视为原点和平面给定点之间的距离。

示例

输入

points = {{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}}, K = 4

输出

{2,1} {2,-2} {0,3} {-5,1}

Explanation − 这里是每个点到原点的欧几里得距离。

• (2, −2) −> sqrt(8)

• (−5, 1) −> sqrt(26)

• (2, 1) -> sqrt(5)

• (0, 3) −> sqrt(9)

• (6, 0) -> sqrt(36)

• (5, 5) -> sqrt(50)

• (4, 9) -> sqrt(97)

因此，4 个最近的点是 {2,1} {2,−2} {0,3} {−5,1}。

输入

points = {{1, 2}, {2, 1}, {-2, 1}, {1, -2}} K = 2

输出

{1, 2}, {2, 1}

Explanation − 所有点到原点的距离都是相同的。因此，我们可以将任意2个点作为输出打印。

输入

points = {{1, 3}, {6, 7}, {1, 1}, {1, 0}} K = 4

输出

{1, 0}, {1, 1}, {1, 3}, {6, 7}

解释− K 等于给定点。因此，我们需要打印所有点。

Spell.tools

高颜值AI内容营销创作工具

下载

方法一

在这种方法中，我们将使用 sort() 方法对数组进行排序。此外，我们将使用比较器函数根据点与原点的距离对点进行排序。之后，我们打印排序数组的前 K 个元素。

算法

步骤 1 − 使用sort()方法对列表进行排序，并将distComparator()函数作为第三个参数传递。

第二步− 定义distComparator()函数来比较给定点的距离。该函数以p和q对作为参数。

步骤 2.1 − 获取点 p 到原点的距离并将其存储在 dist_p 中。

步骤 2.2 − 将点 q 到原点的距离存储在 dist_q 变量中。

步骤 2.3 − 如果 dist_p 小于 dist_q，则返回 true。否则，返回 false。

第 3 步- 遍历数组，并打印数组的前 K 个点。

示例

#include 
using namespace std;

bool distComparator(const pair &p, const pair &q) {
    int dist_p = p.first * p.first + p.second * p.second;
    int dist_q = q.first * q.first + q.second * q.second;
    return dist_p < dist_q;
}
vector> findKPoints(vector> points, int n, int k) {
    vector> res_points;
    sort(points.begin(), points.end(), distComparator);
    // Get the first K points
    for (int p = 0; p < k; p++)     {
        res_points.push_back({points[p].first, points[p].second});
    }
    return res_points;
}
int main() {
    int k = 4, n = 7;
    vector> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector> res = findKPoints(points, n, k);
    cout << "The " << k << " closest points from origin are - ";
    for (int p = 0; p < k; p++) {
        cout << "{" << res[p].first << "," << res[p].second << "} ";
    }
    return 0;
}

输出

The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

时间复杂度 - 对数组进行排序的时间复杂度为O(NlogN)。

空间复杂度 - O(N) 用于对数组进行排序。

方法二

在这种方法中，我们将使用优先级队列来插入点。此外，我们将使用比较器函数和优先级队列来根据距原点的最短距离来存储点。

算法

步骤 1 − 定义‘res_points’列表，用于存储K个最近的点。

步骤 2- 定义优先级队列。这里，‘pair’表示使用优先级队列来存储整数对。 ‘vector>’表示使用向量来存储对。此外，我们还使用了带有优先级队列的“cmp”函数。

第三步− 定义cmp()函数来比较两个点到原点的欧几里得距离。

步骤 3.1 - 根据 a 点到原点的距离大于 b 点到原点的距离，返回布尔值。

第 4 步- 将数组的每个元素插入优先级队列。

第5步− 从队列中弹出前K个元素，并将它们存储在res_points列表中。

第 6 步− 返回点的 res_points 列表。

示例

#include 
using namespace std;

vector> findKPoints(vector> points, int n, int k) {
    vector> res_points;
    // Custom comparator to compare points based on their distance from the origin
    auto cmp = [](const pair& a, const pair& b) {
        return (a.first * a.first + a.second * a.second) > (b.first * b.first + b.second * b.second);
    };
    // Use the custom comparator in the priority_queue
    priority_queue, vector>, decltype(cmp)> p_que(cmp);
    for (int p = 0; p < n; p++) {
        // Inserting points in a queue
        p_que.push(points[p]);
    }
    // Get first K points
    while (k--) {
        auto temp = p_que.top();
        res_points.push_back(temp);
        p_que.pop();
    }
    return res_points;
}
int main() {
    int k = 4, n = 7;
    vector> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector> res = findKPoints(points, n, k);
    cout << "The " << k << " closest points from origin are - ";
    for (int p = 0; p < k; p++) {
        cout << "{" << res[p].first << "," << res[p].second << "} ";
    }
    return 0;
}

输出

The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

时间复杂度 - O(N*logN) 将 N 个元素插入优先级队列。这里，N是总点数。

空间复杂度 - 在优先级队列中存储点的 O(N)。

优先队列使用堆数据结构。因此，插入和删除元素只需O(logN)的时间。这两种方法都需要相同的内存和时间。然而，第二种方法更高效，因为它使用了堆数据结构。