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

浅明小哥_5425

浅明小哥_5425

2023-09-14

1456人浏览

转载

使用优先队列找到离原点最近的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 等于给定点。因此,我们需要打印所有点。

奇布塔
奇布塔

一款面向有声绘本创作的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 <bits>
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 > findKPoints(vector<pair int>> points, int n, int k) {
    vector<pair int>> res_points;
    sort(points.begin(), points.end(), distComparator);
    // Get the first K points
    for (int p = 0; p > points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair int>> res = findKPoints(points, n, k);
    cout <h3>输出</h3><pre class="brush:php;toolbar:false;">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 <bits>
using namespace std;

vector<pair int>> findKPoints(vector<pair int>> points, int n, int k) {
    vector<pair 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>, vector<pair int>>, decltype(cmp)> p_que(cmp);
    for (int p = 0; p > points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair int>> res = findKPoints(points, n, k);
    cout <h3>输出</h3><pre class="brush:php;toolbar:false;">The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

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

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

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

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
sort排序函数用法
sort排序函数用法

sort排序函数的用法:1、对列表进行排序,默认情况下,sort函数按升序排序,因此最终输出的结果是按从小到大的顺序排列的;2、对元组进行排序,默认情况下,sort函数按元素的大小进行排序,因此最终输出的结果是按从小到大的顺序排列的;3、对字典进行排序,由于字典是无序的,因此排序后的结果仍然是原来的字典,使用一个lambda表达式作为key参数的值,用于指定排序的依据。

2023.09.04

1158

7

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2941

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

堆和栈的区别
堆和栈的区别

堆和栈的区别:1、内存分配方式不同;2、大小不同;3、数据访问方式不同;4、数据的生命周期。本专题为大家提供堆和栈的区别的相关的文章、下载、课程内容,供大家免费下载体验。

2023.07.18

7127

5

堆和栈区别
堆和栈区别

堆(Heap)和栈(Stack)是计算机中两种常见的内存分配机制。它们在内存管理的方式、分配方式以及使用场景上有很大的区别。本文将详细介绍堆和栈的特点、区别以及各自的使用场景。php中文网给大家带来了相关的教程以及文章欢迎大家前来学习阅读。

2023.08.10

2908

6

页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

2023.08.14

7216

4

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习