堆排序 VS 快速排序 解决 TOP K 问题

1 templateclass _Ty1, class _Ty2>
2  inline  bool operatorconst pair<_ty1 _ty2>& _Left, 
3                                   const pair<_ty1 _ty2>& _Right)
4     {    // test if _Left 
5     return (_Left.first 6         !(_Right.first  _Right.second);
7     }

 1 class Solution {
 2 public:
 3     vectorint>> kClosest(vectorint>>& points, int k)
 4     {
 5         const int n = points.size();
 6         vectorint> index_vec(n);
 7         for(int i = 0 ; i i)
 8         {
 9             index_vec[i] = i;
10         }
11         int left = 0, right = n - 1;
12         bool flag = false;
13         while(left  right)
14         {
15             int t = partition(points,index_vec,left,right);
16             if(t == -1) break;
17             if(t == k - 1)
18             {
19                 flag = true;
20                 break;
21             }
22             else if( t > k - 1)
23             {
24                 right = t - 1;
25             }
26             else
27             {
28                 left = t + 1;
29             }
30         }
31         vectorint>> res;
32         if(flag)
33         {
34             for(int i = 0;i i)
35             {
36                 res.push_back(points[index_vec[i]]);
37             }
38         }
39         return res;
40     }
41     
42     int partition(vectorint>>& points,vectorint> &index_vec,int l,int r)
43     {
44         if(l > r)
45         {
46             return -1;
47         }
48         int i = l,j = r;
49         int pivot = cal_dist(points[index_vec[l]]);
50         while( true )
51         {
52             while(i i;
53             while(i = pivot) --j;
54             if(i > j)
55             {
56                 break;
57             }
58             std::swap(index_vec[i],index_vec[j]);
59         }
60         std::swap(index_vec[l],index_vec[j]);//最后一次交换 index_vec[l] 最终的位置确定
61         return j;
62     }
63     
64     inline int cal_dist(vectorint>& point)
65     {
66         return point[0] * point[0] + point[1] * point[1];
67     }
68 };

 1 //Top K we
 2   class my_less {
 3     public:
 4         bool operator()(const pairint, int>& pr1, const pairint, int>& pr2) {
 5             return pr1.first  pr2.first;
 6         }
 7     };
 8 
 9 class Solution {
10 public:
11     vectorint>> kClosest(vectorint>>& points, int K)
12     {
13         //priority_queue,vector>,my_less> q;//大顶堆
14         priority_queueint, int>> q;
15         const int n = points.size();
16         for (int i = 0; i i)
17         {
18             int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
19             if(q.size()  K)
20             {
21                q.push(make_pair(dist,i));
22                 continue;
23             }
24             if (dist  q.top().first)
25             {
26                 q.pop();
27                 q.emplace(dist, i);
28             }
29         }
30         vectorint>> ans;
31         while (!q.empty())
32         {
33             ans.push_back(points[q.top().second]);
34             q.pop();
35         }
36         return ans;
37     }
38 };