Leetcode

973. K Closest Points to Origin

by hooni posted Apr 15, 2020
?

단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

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. 1 <= K <= points.length <= 10000
  2. -10000 < points[i][0] < 10000
  3. -10000 < points[i][1] < 10000


class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        HashMap<Point, Double> hmap = new HashMap<Point, Double>();
        
        for(int i=0; i<points.length; i++){
            int x = points[i][0];
            int y = points[i][1];
            Double dist = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            hmap.put(new Point(x, y), dist);
        }
        
        //priority = -minimum
        PriorityQueue<Map.Entry<Point, Double>> queue 
            = new PriorityQueue<>(Comparator.comparing(e -> -e.getValue()));
        
        for(Map.Entry<Point, Double> item : hmap.entrySet()){
            queue.offer(item);
            if(queue.size() > K){
                queue.poll();
            }
        }
        
        List<Point> list = new ArrayList<Point>();
        while(queue.size() > 0){
            list.add(queue.poll().getKey());
        }
        
        int[][] result = new int[list.size()][2];
        for(int i=0; i<list.size(); i++){
            Point p = (Point)list.get(i);
            result[i][0] = p.x;
            result[i][1] = p.y;
        }
        
        return result;
    }
}


class Point{
    int x;
    int y;
    double distance;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
        this.distance = Double.MAX_VALUE;
    }
    public double getValue(){
        return this.distance;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        //priority = -minimum
        PriorityQueue<Point> queue = new PriorityQueue<>(Comparator.comparing(e -> -e.getValue()));
        
        for(int i=0; i<points.length; i++){
            int x = points[i][0];
            int y = points[i][1];
            
            Point item = new Point(x, y);
            item.distance = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            
            queue.offer(item);
            if(queue.size() > K){
                queue.poll();
            }
        }
        /*
        List<Point> list = new ArrayList<Point>();
        while(queue.size() > 0){
            list.add(queue.poll());
        }
        int[][] result = new int[list.size()][2];
        for(int i=0; i<list.size(); i++){
            Point p = (Point)list.get(i);
            result[i][0] = p.x;
            result[i][1] = p.y;
        }
        */
        int loop = queue.size();
        int[][] result = new int[loop][2];
        for(int i=0; i<loop; i++){
            Point p = (Point)queue.poll();
            result[i][0] = p.x;
            result[i][1] = p.y;
        }
        
        return result;
    }
}


class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int[] dist = new int[points.length];
        
        for(int i=0; i<points.length; i++){
            //int x = points[i][0];
            //int y = points[i][1];
            //dist[i] = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            dist[i] = points[i][0]*points[i][0] + points[i][1]*points[i][1];
        }
        /*
        for(int i=0; i<dist.length; i++){
            for(int j=0; j<dist.length; j++){
                if(dist[i] < dist[j]){
                    int tmp = dist[i];
                    dist[i] = dist[j];
                    dist[j] = tmp;
                }
            }
        }
        */
        Arrays.sort(dist);

        int maxDist = dist[K-1];
        int index = 0;
        
        int[][] result = new int[K][2];
        for(int i=0; i<points.length && index<K; i++){
            int tmp = points[i][0]*points[i][0] + points[i][1]*points[i][1];
            if(tmp <= maxDist){
                //result[index][0] = points[i][0];
                //result[index][1] = points[i][1];
                //index++;
                result[index++] = points[i];
            }
        }
         
        return result;
    }
}


class Point{
    int x;
    int y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}
 
class Solution {
    public int[][] kClosest(int[][] points, int K) {
        HashMap<Point, Double> hmap = new HashMap<Point, Double>();
        List<Point> list = new ArrayList<Point>();
         
        for(int i=0; i<points.length; i++){
            int x = points[i][0];
            int y = points[i][1];
            Double dist = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            hmap.put(new Point(x, y), dist);
        }
         
        for(int i=0; i<K; i++){
            Point minKey = null;
            Double minValue = Double.MAX_VALUE;
            for(Map.Entry item : hmap.entrySet()){
                Double dist = (Double)item.getValue();
                if(dist < minValue){
                    minKey = (Point)item.getKey();
                    minValue = dist;
                }
            }
             
            if(minKey != null){
                list.add(minKey);
                //hmap.put(minKey, Double.MAX_VALUE);
                hmap.remove(minKey);
            }
        }
         
        int[][] result = new int[list.size()][2];
        for(int i=0; i<list.size(); i++){
            Point p = (Point)list.get(i);
            result[i][0] = p.x;
            result[i][1] = p.y;
        }
         
        return result;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        int[][] result = new int[K][2];
        double[] distance = new double[K];
        
        for(int i=0; i<distance.length; i++){
            distance[i] = Double.MAX_VALUE;
        }
        
        for(int i=0; i<points.length; i++){
            int x = points[i][0];
            int y = points[i][1];
            double d = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            
            if(d < distance[K-1]){
                distance[K-1] = d;
                result[K-1][0] = x;
                result[K-1][1] = y;
                
                for(int m=0; m<K-1; m++){
                    for(int n=m; n<K; n++){
                        if(distance[m] > distance[n]){
                            double tmpd = distance[m];
                            distance[m] = distance[n];
                            distance[n] = tmpd;

                            int tmpx = result[m][0];
                            result[m][0] = result[n][0];
                            result[n][0] = tmpx;

                            int tmpy = result[m][1];
                            result[m][1] = result[n][1];
                            result[n][1] = tmpy;
                        }
                    }
                }
            }
        }
        
        return result;
    }
}


class Point{
    int x;
    int y;
    double dist;
    public Point(int x, int y, double dist){
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        LinkedList<Point> list = new LinkedList<Point>();
        
        for(int i=0; i<points.length; i++){
            int x = points[i][0];
            int y = points[i][1];
            //double dist = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            double dist = (x-0)*(x-0) + (y-0)*(y-0);
            Point point = new Point(x, y, dist);
            boolean done = false;
            
            for(int j=0; j<K && j<list.size(); j++){
                Point item = list.get(j);
                if(item.dist > point.dist){
                    list.add(j, point);
                    done = true;
                    break;
                }
            }
            if(done == false && list.size() < K){
                list.add(point);
            }
            
            done = true;
        }
        
        int[][] result = new int[K][2];
        for(int i=0; i<K && i<list.size(); i++){
            Point p = list.get(i);
            result[i][0] = p.x;
            result[i][1] = p.y;
        }
        
        return result;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        TreeMap<Double, Point> tmap = new TreeMap<Double, Point>();
        
        for(int i=0; i<points.length; i++){
            int x = points[i][0];
            int y = points[i][1];
            double distance = Math.sqrt((x-0)*(x-0) + (y-0)*(y-0));
            
            tmap.put(distance, new Point(x, y));
        }
        
        int[][] result = new int[K][2];
        
        Set set = tmap.entrySet();
        Iterator iterator = set.iterator();
        
        for(int i=0; i<K && iterator.hasNext(); i++) {
            Map.Entry item = (Map.Entry)iterator.next();
            Point p = (Point)item.getValue();
            result[i][0] = p.x;
            result[i][1] = p.y;
        }
        
        return result;
    }
}

TreeMap은 키값으로 정렬(이진트리) 되지만 키 중복이 안됨 ㅋㅋ

거리를 키로 사용할 경우 [0,1], [1,0] 거리 같지만 둘 중 하나만 적용 됨.

[문제] https://leetcode.com/problems/k-closest-points-to-origin/