We have a list of points on the plane. Find the K closest points to the origin (0, 0).
(Here, the distance between two points on a plane is the Euclidean distance.)
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in.)
Example 1:
Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest K = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]
(The answer [[-2,4],[3,3]] would also be accepted.)
Note:
1 <= K <= points.length <= 10000-10000 < points[i][0] < 10000-10000 < points[i][1] < 10000
=== Map approach O(n) time and space
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
vector<vector<int>> ans;
if (points.size() == 0 || k == 0) {
return ans;
}
map<int,vector<vector<int>>> mp;
for (auto point : points) {
int dist = pow(point[0], 2) + pow(point[1], 2);
mp[dist].push_back(point);
}
int counter = 0;
for (auto entry : mp) {
for (auto point : entry.second) {
ans.push_back(point);
if (++counter == k) {
return ans;
}
}
}
return ans;
}
};
======== Can use just sorting nlogn by writing comparator.
Or, use priority queue or quick select.
===========
struct comp {
bool operator()(vector<int>& first, vector<int>& second) {
int dist_one = (first[0]*first[0] + first[1]*first[1]);
int dist_two = (second[0]*second[0] + second[1]*second[1]);
return dist_one < dist_two;
}
};
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
if (points.size() <= k) {
return points;
}
priority_queue<vector<int>, vector<vector<int>>, comp> pq;
for (int i = 0; i < k; i++) {
pq.push(points[i]);
}
for (int i = k; i < points.size(); i++) {
int dist_val = dist(points[i]);
if (dist_val < dist(pq.top())) {
pq.pop();
pq.push(points[i]);
}
}
vector<vector<int>> ans;
while (!pq.empty()) {
ans.push_back(pq.top());
pq.pop();
}
return ans;
}
int dist(vector<int> point) {
return (point[0]*point[0] + point[1]*point[1]);
}
};
============== Quick select =========
class Solution {
public:
int distance(vector<int> &a) {
return a[0]*a[0] + a[1]*a[1];
}
int partition(vector<vector<int>>& points, int low, int high) {
int i = low - 1;
vector<int> pivot = points[high];
for (int j = low; j < high; j++) {
if (distance(points[j]) <= distance(pivot)) {
i++;
swap(points[i], points[j]);
}
}
swap(points[i + 1], points[high]);
return (i + 1);
}
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
int low = 0, high = points.size() - 1;
while(low <= high) {
int ind = partition(points, low, high);
if (ind == k - 1) break;
else if (ind < k - 1) low = ind + 1;
else high = ind - 1;
}
return vector<vector<int>>(points.begin(), points.begin() + k);
}
};
========= My attempt (not clean) ====== (above one is better) ======
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
// K select algorithm.
// base cases (size check with k) and other
int size = points.size();
int st = 0, end = size - 1;
helper(points, st, end, k);
vector<vector<int>> ans = vector<vector<int>>(points.begin(), points.begin() + k);
return ans;
}
void helper(vector<vector<int>>& points, int st, int end, int k) {
if (st > end) {
return;
}
int idx = partition(points, st, end);
if (idx == k - 1) {
return;
} else if (idx < k - 1) {
helper(points, idx + 1, end, k);
} else {
helper(points, st, idx - 1, k);
}
}
int partition(vector<vector<int>>& points, int st, int end) {
int iter = st - 1;
int distance = dist(points[end]);
for (int cur = st; cur < end; cur++) {
if (dist(points[cur]) <= distance) {
iter++;
iter_swap(points.begin() + iter, points.begin() + cur);
}
}
iter_swap(points.begin() + iter + 1, points.begin() + end);
return iter + 1;
}
