codekofi
← All questions

K Closest Points to Origin

HardHeap / Priority Queue

The problem

Given points on the plane and a number k, return the k points nearest the origin, measured by ordinary straight-line distance.

The points may be returned in any order.

kClosest({{3,3},{5,-1},{-2,4}}, 2)

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1vector<vector<int>> kClosest(const vector<vector<int>>& points,
2 int k) {
3
4 int n = points.size();
5 priority_queue<pair<int, int>> far;
6
7 for (int i = 0; i < n; i++) {
8
9 int x = points[i][0];
10 int y = points[i][1];
11
12 far.push({x * x + y * y, i});
13
14 if ((int)far.size() > k) {
15 far.pop();
16 }
17 }
18
19 vector<int> ids;
20
21 while (!far.empty()) {
22 ids.push_back(far.top().second);
23 far.pop();
24 }
25
26 sort(ids.begin(), ids.end());
27
28 vector<vector<int>> ans;
29
30 for (int i : ids) {
31 ans.push_back(points[i]);
32 }
33
34 return ans;
35}
1vector<vector<int>> kClosest(const vector<vector<int>>& points,
2 int k) {
3
4 int n = points.size();
5 priority_queue<pair<int, int>> far;
6
7 for (int i = 1; i < n; i++) {
8
9 int x = points[i][0];
10 int y = points[i][1];
11
12
13 if ((int)far.size() > k) {
14 far.pop();
15 }
16 }
17
18 vector<int> ids;
19
20 while (!far.empty()) {
21 ids.push_back(far.top().second);
22 far.pop();
23 }
24
25 sort(ids.begin(), ids.end());
26
27 vector<vector<int>> ans;
28
29 for (int i : ids) {
30 ans.push_back(points[i]);
31 }
32
33 return ans;
34}
1vector<vector<int>> kClosest(const vector<vector<int>>& points,
2 int k) {
3
4 int n = points.size();
5 priority_queue<pair<int, int>> far;
6
7 for (int i = 1; i < n; i++) {
8
9 int x = points[i][0];
10 int y = points[i][1];
11
12
13 if ((int)far.size() > k) {
14 }
15 }
16
17 vector<int> ids;
18
19 while (!far.empty()) {
20 ids.push_back(far.top().second);
21 far.pop();
22 }
23
24 sort(ids.begin(), ids.end());
25
26 vector<vector<int>> ans;
27
28 for (int i : ids) {
29 ans.push_back(points[i]);
30 }
31
32 return ans;
33}