forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LC_973_KClosestPointsToOrigin.cpp
88 lines (79 loc) · 2.15 KB
/
LC_973_KClosestPointsToOrigin.cpp
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/*
https://leetcode.com/problems/k-closest-points-to-origin/
973. K Closest Points to Origin
*/
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
auto euclidean = [&](auto &p)
{
return p[0]*p[0] + p[1]*p[1];
};
/*
// Using Sort function, lambda function
sort(begin(points), end(points), [&](auto& a, auto& b)
{
return euclidean(a) < euclidean(b);
});
points.resize(k); // resize number of rows.
// for(auto x: points)
// cout<<x[0]<<" "<<x[1]<<" ";
return points;
*/
/*
//Using Max Heap
vector<vector<int>> ans(k);
priority_queue<pair<int,int>> pq;
for(int i=0; i<size(points); i++)
{
pq.emplace(euclidean(points[i]), i);
if(pq.size()>k)pq.pop();
}
for(int i=0; i<k; i++)
{
ans[i] = points[pq.top().second];
pq.pop();
}
return ans;
*/
/*
// Using Randomized select parition
int l=0;
int r=points.size()-1;
while(l<r)
{
int pos = partition(points, l, r);
if(pos == k) break;
if(pos < k) l = pos+1;
else r = pos-1;
}
points.resize(k);
return points;
*/
/*
// Using nth element
nth_element(points.begin(), points.begin()+k, points.end(), [&](auto& a, auto& b){
return euclidean(a) < euclidean(b);
});
points.resize(k);
return points;
*/
}// end
int partition(vector<vector<int>>&P , int low, int high)
{
auto euclidean = [&](auto& p) {return p[0]*p[0]+p[1]*p[1];};
srand(time(0));
swap(P[low], P[low + rand()%(high-low+1)]);
int j = low;
int X = euclidean(P[low]);
for(int i=low+1; i<=high; i++)
{
if(euclidean(P[i]) < X)
{
swap(P[i], P[++j]);
}
}
swap(P[j], P[low]);
return j;
}
};