【免费】手稿_V1.119资源-CSDN文库

需积分: 0 149 浏览量 2022-08-03 15:43:44 上传评论收藏 210KB PDF 举报

资源详情

资源评论

资源推荐

分析:

方法一:

筛选前个的问题,首先想到的是优先队列这个数据结构,要筛选出前小的问题,想到了使用小顶堆,

由于要比较的是距离,所以想到了pair这个数据结构.

由于欧氏距离与平方和成正相关关系,且 ,所以比较对象使用

unsigned long 类型即可,不需要用到浮点运算.

方法二:

维护一个容量只有的大顶堆,最后将个数据出堆,然后为了保证顺序一下即可.



Ref(向两篇文章的作者致谢):

queue pair

priority_queue 中存放pair时，自定义排序的写法

/*

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

（这里，平面上两点之间的距离是欧几里德距离。）

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

示例 1：

输入：points = [[1,3],[-2,2]], K = 1

输出：[[-2,2]]

解释：

(1, 3) 和原点之间的距离为 sqrt(10)，

(-2, 2) 和原点之间的距离为 sqrt(8)，

由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。

我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], K = 2

输出：[[3,3],[-2,4]]

（答案 [[-2,4],[3,3]] 也会被接受。）

提示：

 1 <= K <= points.length <= 10000

 -10000 < points[i][0] < 10000

 -10000 < points[i][1] < 10000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/k-closest-points-to-origin

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

评论0

内容反馈

申增浩

粉丝: 20
资源: 297

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip