Leetcode: 973. K Closest Points to Origin (customized comparator)

Question:

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]].

Note:

We can use PriorityQueue to solve problem, but the point is customize the comparator.

Solution:

class Solution {
	public class DPoint{
		int xCoor, yCoor;
		double disFromOrigin;
		public DPoint(int x, int y) {
            xCoor = x;
            yCoor = y;
            disFromOrigin = Math.sqrt(x*x + y*y);
        }
	}
	
	public class PointDistanceComparator implements Comparator<DPoint> {
		@Override
		public int compare(DPoint x, DPoint y) {
			if (x.disFromOrigin < y.disFromOrigin) {
                return -1;
            }
            if (x.disFromOrigin > y.disFromOrigin) {
                return 1;
            }
            return 0;
		}
	}
    public int[][] kClosest(int[][] points, int K) {
        Comparator<DPoint> comparator = new PointDistanceComparator();
        Queue<DPoint> queue = new PriorityQueue<DPoint>(10, comparator);
        for (int i = 0; i < points.length; i++) {
            queue.add(new DPoint(points[i][0], points[i][1]));
        }
        int[][] ans = new int[K][2];
        for (int i = 0; i < K; i++) {
            ans[i][0] = queue.peek().xCoor;
            ans[i][1] = queue.poll().yCoor;
        }
        return ans;
    }
}
           

Time Complexity:

1. Insertion into PQ: O(log(n))
2. peek(): K
3. poll:O(Klong(n))