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

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

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

然而，我们也可以使用优先队列来根据离原点的距离存储2D点。然后，我们可以从队列中deque出K次。

问题陈述 − 我们在2D平面中有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}

解释 − 这是每个点到原点的欧几里德距离。

• (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}

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

输入

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

输出

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

解释 − K等于给定的点的数量。所以，我们需要打印所有的点。

方法1

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

步骤

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

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

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

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

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

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

示例

#include <bits/stdc++.h>
using namespace std;

bool distComparator(const pair<int, int> &p, const pair<int, int> &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<pair<int, int>> findKPoints(vector<pair<int, int>> points, int n, int k) {
    vector<pair<int, int>> 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<pair<int, int>> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair<int, int>> 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)。

方法2

在这个方法中，我们将使用优先队列来插入点。同时，我们将使用带有优先队列的比较器函数来根据它们离原点的最短距离来存储点。

步骤

第1步 -定义’res_points’列表以存储前K个最近的点的对。

第2步 -定义优先队列。这里，’pair’表示使用优先队列来存储整数对。’vector>’表示使用向量来存储这些对。同时，我们使用了带有优先队列的’cmp’函数。

第3步 -定义’cmp()’函数来比较两个点与原点之间的欧几里德距离。

第3.1步 -根据点a与点b与原点之间的距离返回布尔值。

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

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

第6步 -返回点的’res_points’列表。

示例

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> findKPoints(vector<pair<int, int>> points, int n, int k) {
    vector<pair<int, int>> res_points;
    // Custom comparator to compare points based on their distance from the origin
    auto cmp = [](const pair<int, int>& a, const pair<int, int>& 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<pair<int, int>, vector<pair<int, int>>, 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<pair<int, int>> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair<int, int>> 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}

时间复杂度 – 将N个元素插入到优先队列中的时间复杂度是O(N*logN)。这里，N是所有点的总数。

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

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