数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用优先队列查找距离原点最近的 K 个点
在这个问题中，我们将从给定的 N 个点中找到二维平面中距离原点最近的 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}
说明 - 以下是每个点到原点的欧几里得距离。
(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<int, int>’ 表示使用优先队列存储整数对。‘vector<pair<int, int>>’ 表示使用向量存储对。此外，我们使用了 ‘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) 时间。两种方法都占用相同内存和时间。但是，第二种方法更有效，因为它使用堆数据结构。
177 次查看
