LintCode 401. Kth Smallest Number in Sorted Matrix

http://www.lintcode.com/en/problem/kth-smallest-number-in-sorted-matrix/



Find the kth smallest number in at row and column sorted matrix.
Example
Given k = 4 and a matrix:
[
[1 ,5 ,7],
[3 ,7 ,8],
[4 ,8 ,9],
]
return 5

	public class Solution {
	/**
	* @param matrix: a matrix of integers
	* @param k: an integer
	* @return: the kth smallest number in the matrix
	*/
	public int kthSmallest(int[][] matrix, int k) {
	// write your code here
	// handle extreme cases
	if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
	return -1;
	}
	if (k == 0) {
	return -1;
	}
	int n = matrix.length;
	int m = matrix[0].length;
	PriorityQueue<Cell> heap = new PriorityQueue<Cell>(n, cellComparator);
	for (int i = 0; i < n; i++) {
	heap.add(new Cell(matrix[i][0], i, 0));
	}
	for (int i = k; i > 1; i--) {
	Cell poll = heap.poll();
	if (poll.y < m - 1) {
	heap.add(new Cell(matrix[poll.x][poll.y + 1], poll.x, poll.y + 1));
	}
	}
	if (heap.isEmpty()) {
	return -1;
	} else {
	return heap.poll().val;
	}
	}
	Comparator<Cell> cellComparator = new Comparator<Cell>() {
	public int compare(Cell o1, Cell o2) {
	return o1.val - o2.val;
	}
	};
	private class Cell {
	int val;
	int x;
	int y;
	public Cell() {
	}
	public Cell(int val, int x, int y) {
	this.val = val;
	this.x = x;
	this.y = y;
	}
	}
	}

view raw LintCode 401. Kth Smallest Number in Sorted Matrix.java hosted with ❤ by GitHub