鱼C论坛

 找回密码
 立即注册
查看: 2359|回复: 1

[技术交流] C++刷leetcode(973. 最接近原点的 K 个点)【数据结构】

[复制链接]
发表于 2020-5-18 12:42:27 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。

  2. (这里,平面上两点之间的距离是欧几里德距离。)

  3. 你可以按任何顺序返回答案。除了点坐标的顺序之外,答案确保是唯一的。

  4.  

  5. 示例 1:

  6. 输入:points = [[1,3],[-2,2]], K = 1
  7. 输出:[[-2,2]]
  8. 解释:
  9. (1, 3) 和原点之间的距离为 sqrt(10),
  10. (-2, 2) 和原点之间的距离为 sqrt(8),
  11. 由于 sqrt(8) < sqrt(10),(-2, 2) 离原点更近。
  12. 我们只需要距离原点最近的 K = 1 个点,所以答案就是 [[-2,2]]。
  13. 示例 2:

  14. 输入:points = [[3,3],[5,-1],[-2,4]], K = 2
  15. 输出:[[3,3],[-2,4]]
  16. (答案 [[-2,4],[3,3]] 也会被接受。)
  17. &#160;

  18. 提示:

  19. 1 <= K <= points.length <= 10000
  20. -10000 < points[i][0] < 10000
  21. -10000 < points[i][1] < 10000

  22. 来源:力扣(LeetCode)
  23. 链接:https://leetcode-cn.com/problems/k-closest-points-to-origin
  24. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. class Solution {
  2.     struct cmp{
  3.         bool operator()(pair<int, vector<int>>&a, pair<int, vector<int>>&b){
  4.             return a.first > b.first;
  5.         }
  6.     };
  7. public:
  8.     vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
  9.         vector<vector<int> > res;
  10.         priority_queue<pair<int, vector<int>>,vector<pair<int, vector<int>>>, cmp> temp;
  11.         int distance;
  12.         for(auto cha : points){
  13.             distance = pow(cha[0], 2) + pow(cha[1], 2);
  14.             temp.push(std::make_pair(distance, cha));
  15.         }

  16.         while(K--){
  17.             res.push_back(temp.top().second);
  18.             temp.pop();
  19.         }

  20.         return res;
  21.     }
  22. };
复制代码


注意:
1.cmp的书写!

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-5-18 12:43:49 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-5 22:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表