Java klog(k) 37ms solution with heap


  • 0
    G
    public int kthSmallest(int[][] matrix, int k) {
    		if(matrix == null || matrix.length == 0) return 0;
    		PriorityQueue<int[]> pq = new PriorityQueue< >(3, new Comparator<int[]>(){
    			public int compare(int[] a1, int[] a2){
    				return  (a1[0]  - a2[0]);
    			}
    		});
    		int[] cur = new int[3]; // cur[0] : matrix[rindex][cindex], cur[1]: rowIndex, cur[2]: colIndex
    		for (int j = 0; j < matrix[0].length && j < k; j++)  {
    			pq.offer(new int[]{matrix[0][j], 0, j});
    		}
    		while (k > 0 && !pq.isEmpty()) {
    			cur = pq.poll();
    			int rindex = cur[1];
    			int cindex = cur[2];
    			if (rindex < matrix.length - 1) {
    				pq.offer(new int[]{matrix[rindex+1][cindex], rindex + 1, cindex});
    			}
    			k--;
    		}
    		return cur[0];
    	}

Log in to reply
 

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