Concise Java O(klgn) solution


  • 0
    J
    class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> matrix[a[0]][a[1]] - matrix[b[0]][b[1]]);
            int n = matrix.length;
            for (int i = 0; i < n; i++) pq.offer(new int[]{i,0});
            for (int i = 0; i < k - 1; i++) {
                int[] cood = pq.poll();
                if (++cood[1] < n) pq.offer(cood);
            }
            int[] cood = pq.poll();
            return matrix[cood[0]][cood[1]];
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.