KClosest

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

• 우선순위 큐 , 람다를 씀.
• 각 원소의 제곱의 합의 제곱근을 비교해서 정렬시킴
• 정렬은 내부 이진트리구조에서 정렬될테니 for 문을 돌려서 그대로 원소를 추가 함.
• index 로 while 문 탈출 플레그를 잡는다.
• 순환만큼 answer에 값을 대입한다.
• 리턴

/**
     * 원점 0,0 으로 부터 두 원소의 제곱을 더한 값의 제곱근을 비교해서 작은 것을 리턴
     * @param points
     * @param k
     */
    private static void solve(int[][] points, int k) {
        Queue<int[]> minHeap = new PriorityQueue<>(points.length,
        (o1, o2) -> {
                        int x = (0 - o1[0]) * (0 - o1[0]);
                        int y = (0 - o1[1]) * (0 - o1[1]);
                        double sqt1 = Math.sqrt(x+y);
                        x = (0 - o2[0]) * (0 - o2[0]);
                        y = (0 - o2[1]) * (0 - o2[1]);
                        double sqt2 = Math.sqrt(x+y);
                        if(sqt1 < sqt2)
                            return -1;
                        else if (sqt1 == sqt2)
                            return 0;
                        else
                            return 1;
                });

        for(int i=0; i<points.length; i++){
            minHeap.offer(points[i]);
        }

        int[][] answer = new int[k][2];
        int count =0;
        while(count < k){
            int[] token = minHeap.poll();
            answer[count] = token;
            count ++;
        }
        System.out.println(Arrays.deepToString(answer));
    }

---

• 동일하게 우선순위 큐 쓰심
• 제곱으로만 우선순위 큐를 작성하심
• 동일.

private static void solve(int[][] points, int k) {

        Comparator<int[]> Comp = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                //제곱으로만 우선순위큐 생성
                return (o1[0]*o1[0] +o1[1] * o1[1]) - (o2[0]*o2[0] +o2[1] * o2[1]);
            }
        };
        Queue<int[]> queue = new PriorityQueue<>(points.length, Comp);

        int[][] result = new int[k][2];
        int index = 0;

        for(int[] p : points){
            queue.offer(p);
        }
        while(index < k){
            result[index] = queue.poll();
            index++;
        }
        System.out.println(Arrays.deepToString(result));
    }

 

거의 동일했다. 조금이라도 동일하게 풀었다는게 정말 감사한 일이다.