排序矩阵中从小到大第k个数

题目描述

在一个排序矩阵中找从小到大的第 k 个整数。
排序矩阵的定义为：每一行递增，每一列也递增。

思路

用堆。
将矩阵中的第一列元素加入堆中
从堆中取出最小元素，再将该元素所在数组的下一个元素加入堆中，重复k次

代码

public int kthSmallest(int[][] matrix, int k) {
       // write your code here
	if(matrix.length == 0) {
		return -1;
	}
	PriorityQueue<Element> heap = new PriorityQueue<>();
	int row = matrix.length;
	for(int j = 0; j < row; j++) {
		heap.add(new Element(j, 0, matrix[j][0]));
	}
	int count = 1; 
	while(count < k) {
	    if(heap.size() == 0) {
	        break;
	    }
		Element top = heap.poll();
		count++;
		if(top.col == matrix[0].length-1) {
		    continue;
		}
		heap.add(new Element(top.row, top.col+1, matrix[top.row][top.col+1]));
	}
	if(count < k) {
	    return -1;
	}
	return heap.poll().val;
}

class Element implements Comparable<Element>{
   	public int val;
   	public int col;
   	public int row;
   	public Element(int row, int col, int val) {
   		this.row = row;
   		this.col = col;
   		this.val = val;
   	}
	@Override
	public int compareTo(Element o) {
		// TODO Auto-generated method stub
		return this.val > o.val ? 1 :  
			   this.val < o.val ? -1 : 0;
	}
   }

考差点

• 堆