Java

  • import java.util.Arrays;
    import java.util.PriorityQueue;
    
    /**
    
     973. K Closest Points to Origin
    
     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
    
     @tag-trie
    
     */
    
    // @todo: divide and conquer solution
    public class K_Closest_Points_to_Origin {
    
        public static void main(String[] args) {
            K_Closest_Points_to_Origin out = new K_Closest_Points_to_Origin();
            Solution s = out.new Solution();
    
            System.out.println(Arrays.toString(s.kClosest(new int[][]{ {3,3},{5,1},{-2,4} }, 2)));
        }
    
        class Solution {
            public int[][] kClosest(int[][] points, int K) {
                PriorityQueue<int[]> pq = new PriorityQueue<int[]>(
                    // larger at top
                    (p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]
                );
    
                for (int[] p : points) {
                    pq.offer(p);
                    if (pq.size() > K) {
                        pq.poll();
                    }
                }
    
                int[][] res = new int[K][2];
    
                while (K > 0) {
                    res[--K] = pq.poll();
                }
    
                return res;
            }
    
        }
    }
    
  • // OJ: https://leetcode.com/problems/k-closest-points-to-origin/
    // Time: O(NlogN)
    // Space: O(1)
    class Solution {
    private:
        int dist(vector<int> &p) {
            return p[0] * p[0]  + p[1] * p[1];
        }
    public:
        vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
            sort(points.begin(), points.end(), [&](auto &a, auto &b) { return dist(a) < dist(b); });
            return vector<vector<int>>(points.begin(), points.begin() + K);
        }
    };
    
  • class Solution(object):
        def kClosest(self, points, K):
            """
            :type points: List[List[int]]
            :type K: int
            :rtype: List[List[int]]
            """
            dis = []
            for p in points:
                d = math.sqrt(p[0] ** 2 + p[1] ** 2)
                dis.append((d, p))
            heapq.heapify(dis)
            return [d[1] for d in heapq.nsmallest(K, dis)]
    

Java

  • class Solution {
        public int[][] kClosest(int[][] points, int K) {
            Arrays.sort(points, new Comparator<int[]>() {
                public int compare(int[] point1, int[] point2) {
                    return (point1[0] * point1[0] + point1[1] * point1[1]) - (point2[0] * point2[0] + point2[1] * point2[1]);
                }
            });
            int[][] closestPoints = new int[K][2];
            for (int i = 0; i < K; i++) {
                for (int j = 0; j < 2; j++)
                    closestPoints[i][j] = points[i][j];
            }
            return closestPoints;
        }
    }
    
  • // OJ: https://leetcode.com/problems/k-closest-points-to-origin/
    // Time: O(NlogN)
    // Space: O(1)
    class Solution {
    private:
        int dist(vector<int> &p) {
            return p[0] * p[0]  + p[1] * p[1];
        }
    public:
        vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
            sort(points.begin(), points.end(), [&](auto &a, auto &b) { return dist(a) < dist(b); });
            return vector<vector<int>>(points.begin(), points.begin() + K);
        }
    };
    
  • class Solution(object):
        def kClosest(self, points, K):
            """
            :type points: List[List[int]]
            :type K: int
            :rtype: List[List[int]]
            """
            dis = []
            for p in points:
                d = math.sqrt(p[0] ** 2 + p[1] ** 2)
                dis.append((d, p))
            heapq.heapify(dis)
            return [d[1] for d in heapq.nsmallest(K, dis)]
    

All Problems

All Solutions