1.暴力排序，新建节点类重载小于符号排序。
class Solution {
public:
struct comb{
int index,distance;
comb():index(0),distance(0){}
comb(int a,int b){
index=a;distance=b;
}
bool operator<(const comb& x){
return distance<x.distance;
}
};
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
if(points.size()<=K){
return points;
}
vector<comb> vec(points.size());
for(int i=0;i<points.size();++i){
vec[i]=comb(i,points[i][0]*points[i][0]+points[i][1]*points[i][1]);
}
sort(vec.begin(),vec.end());
vector<vector<int>> res(K);
for(int i=0;i<K;++i){
res[i]=points[vec[i].index];
}
return res;
}
};
其实我是想只对索引数组进行排序的，但sort的重载小于符函数不大好写，因为要用到points数组，没法加到函数参数里，所以就先这样写
2.快排划分。想到没必要全排序，因为只需要前k个。若当前划分好的小于K个，到右边再找。若等于K个或者K-1个，则输出。否则到左边缩小划分继续找，O(N logN)时间（大概是这个，具体不会算）。
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K)
{
int siz = points.size();
if(K==siz)
{
return points;
}
vector<int> indexes(siz);
for (int i = 0; i < siz; ++i)
{
indexes[i] = i; //存索引
}
vector<vector<int>> res;
quicksort(indexes, points, 0, siz - 1, K, res);
return res;
}
void quicksort(vector<int>& indexes, vector<vector<int>>& points, int le, int ri, const int& K, vector<vector<int>>& res)
{
if (res.size() or le > ri)
{
return;
}
int mi = partition(indexes, points, le, ri, K);
if (mi == K - 1)
{
res.resize(K);
for (int i = 0; i < K; ++i)
{
res[i] = points[indexes[i]];
}
return;
}
else if (mi < K - 1) //目前找到最小的mi+1个，但mi+1<k，所以还要到右半边找k-mi+1个
{
quicksort(indexes, points, mi + 1, ri, K, res);
}
else //mi>k-1，则mi+1>k，左半边元素大于K个
{
quicksort(indexes, points, le, mi - 1, K, res);
}
}
int partition(vector<int>& indexes, vector<vector<int>>& points, int le, int ri, const int& K)
{
if(le==ri)
{
return le;
}
int p = le + rand() % (ri - le + 1);
int temp = indexes[p];
indexes[p] = indexes[ri];
indexes[ri] = temp;
int i = le - 1, j = le;
while (j < ri)
{
if (check(indexes[j], indexes[ri], points)) //索引j对应的点离原点比基准点近
{
int temp = indexes[j];
indexes[j] = indexes[++i];
indexes[i] = temp; //i先+1,再交换i、j处的索引值
}
++j;
}
temp = indexes[i + 1];
indexes[i + 1] = indexes[ri];
indexes[ri] = temp;
return i + 1; //返回基准数位置
}
bool check(int i, int j, vector<vector<int>>& points) //i、j为points的索引
{
if (abs(points[i][0]) < abs(points[j][0]) and abs(points[i][1]) < abs(points[j][1]))
{
return true;
}
return pow(points[i][0], 2) + pow(points[i][1], 2) < pow(points[j][0], 2) + pow(points[j][1], 2);
}
};
3.堆排。考虑到要求的前k个元素并不要求有序，故考虑建长度K的大顶堆，将所有点依次加入直到堆满。之后若当前元素比堆顶还大，丢弃该元素不用。最后留下来的K个就是最小的K个。这K个不是完全有序的，但确实是最小的K个。O(N logK)时间。
class Solution {
public:
static bool cmp(const vector<int>& a, vector<int>& b) {
return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
};
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
if (K >= points.size()) {
return points;
}
vector<vector<int>>res;
make_heap(res.begin(),res.end(),cmp); //大顶堆
for (auto& point : points) {
if (res.size() >= K) {
if(cmp(point,res[0])){ //当前point小于堆顶，pop堆顶，push当前point
pop_heap(res.begin(), res.end(),cmp);
res.pop_back();
res.push_back(point);
push_heap(res.begin(), res.end(), cmp);
}
}
else{
res.push_back(point);
push_heap(res.begin(), res.end(), cmp);
}
}
return res;
}
};