K Closest Points to Origin using Custom Sorting Algorithm in C++
- 时间:2020-09-09 13:08:38
- 分类:网络文摘
- 阅读:80 次
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.)
In K Closest Points to Origin Algorithm by using Priority Queues in C++/Java, we have solved the problem by using a priority queue in C++/Java. This post will focus on solving the same problem using the custom sorting algorithm.
C++ Program to Compute K Closest Points to Origin using Custom Sorting Algorithm
C++’s sort method allows a third parameter as the custom comparator.
1 2 3 4 5 6 7 8 9 10 11 | class Solution { public: vector<vector<int>> kClosest(vector<vector<int>>& points, int K) { sort(begin(points), end(points), [](auto &a, auto &b) { auto d1 = a[0] * a[0] + a[1] * a[1]; auto d2 = b[0] * b[0] + b[1] * b[1]; return d1 < d2; }); return vector(begin(points), begin(points) + K); } }; |
class Solution { public: vector<vector<int>> kClosest(vector<vector<int>>& points, int K) { sort(begin(points), end(points), [](auto &a, auto &b) { auto d1 = a[0] * a[0] + a[1] * a[1]; auto d2 = b[0] * b[0] + b[1] * b[1]; return d1 < d2; }); return vector(begin(points), begin(points) + K); } };
Then we can use the vector constructor (giving it two iterators start and finish) to return a copy of the vector.
Java Program to Compute K Closest Points to Origin using Custom Sorting Algorithm
In Java, we can use Arrays.sort method to sort the int[][] object. We can then use Arrays.copyOfRange to return a copy of the sub array (substring on Array).
1 2 3 4 5 6 7 8 9 10 | class Solution { public int[][] kClosest(int[][] points, int K) { Arrays.sort(points, (a, b) -> { int x = a[0] * a[0] + a[1] * a[1]; int y = b[0] * b[0] + b[1] * b[1]; return x - y; }); return Arrays.copyOfRange(points, 0, K); } } |
class Solution { public int[][] kClosest(int[][] points, int K) { Arrays.sort(points, (a, b) -> { int x = a[0] * a[0] + a[1] * a[1]; int y = b[0] * b[0] + b[1] * b[1]; return x - y; }); return Arrays.copyOfRange(points, 0, K); } }
Both implementations have O(N.LogN) time complexity which is what a sorting algorithm would cost nowadays.
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:世界上最昂贵的10种食物大盘点 营养丰富的西红柿鸡蛋汤两种做法 毛豆膳食纤维含量高这样吃最营养 细说蔬菜甘蓝的四大营养保健价值 饮食与健康:十大抗癌食物排行榜 三款适合秋季食用的润燥养生粥 火锅汤底搭配凉性食材不容易上火 紫薯和红薯的营养保健价值比较 秋季5种润秋燥的美味水果最养人 揭秘6种既廉价又抗癌的美味零食
- 评论列表
-
- 添加评论