求教一道题：c++一个2维平面上有一个点P0和其他一堆点(n个),找出距离P0最近的 ...

求教大家一道题，c++，如下：
一个 2维平面上有一个点 P0 和 其他一堆点（n个），找出距离 P0 最近的 k 个点。P0点以及其余N个点的坐标已知，N个点的坐标存在一个二维vector<pair<int,int>>& pts里，P0点的坐标为pair<int,int>& p0，找到距离P0最近的K个点。函数头如下：

vector<pair<int,int>> findKNearstPoint( vector<pair<int,int>>& pts, pair<int,int>& p0, int k ) {}
不会做，请教大家了~

为什么会没有思路？可以先想想暴力方法的对吧。求k个最近的点，也就是找k个距离最短的点。你是不是可以先把n个点的距离都算出来，再找最近的。也就是一共n个距离里找k个最小的对吧。然后topk会做吧？

是不是很自然，LZ看题别慌啊，这样的题都毫无思路话，再多写写代码吧。

Ariel_Dang 发表于 2017-2-22 03:12
请问建堆是什么意思？是不是就是先暴力计算出全部点的距离，然后排序找出前K个？

我猜他的意思可能是堆排序。不过堆排效率应该比快排低吧，所以有可能我还是理解错了。

Ariel_Dang 发表于 2017-2-22 03:12
请问建堆是什么意思？是不是就是先暴力计算出全部点的距离，然后排序找出前K个？

开一个大小为K的堆，计算出一个距离后就扔进堆里，复杂度NlogK。

计算出距离后，建堆

投楼上一票，ps：直接用距离的平方，别开根号，考虑overflow，use long instead of int

最直接就是暴力搞就好了吧

平均O(n)的算法：随机partition

ivanyang 发表于 2017-2-15 12:30
计算出距离后，建堆

请问建堆是什么意思？是不是就是先暴力计算出全部点的距离，然后排序找出前K个？

看着这个题不知怎的就想到了聚类算法