题目要求
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:
matrix = [
[1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
Note:
You may assume k is always valid, 1 ≤ k ≤ n2.
在一个从左到右，从上到下均有序的二维数组中，找到从小到第 k 个数字，这里需要注意，不要求一定要是唯一的值，即假设存在这样一个序列 1,2,2,3，则第三个数字是 2 而不是 3。
思路一：优先队列
当涉及到从一个集合中查找一个元素这样的问题时，我们往往会立刻想到查找的几种方式：有序数组查找，无序数组查找，堆排序。这里如果将二维数组转化为一维有序数组，成本未免太大了。同理，将其中所有元素都转化为堆，也会存在内存不足的问题。因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第 k 个元素的值进行堆排序就可以了。
public int kthSmallest(int[][] matrix, int k) {
// 优先队列
PriorityQueue<Tuple> queue = new PriorityQueue<Tuple>();
// 将每一行的第一个元素放入优先队列中
for(int i = 0 ; i<matrix.length ; i++) {
queue.offer(new Tuple(i, 0, matrix[i][0]));
}
// 对优先队列执行 k 次取操作，取出来的就是第 k 个值
for(int i = 0 ; i<k-1 ; i++) {
Tuple t = queue.poll();
// 判断是否到达行尾，若没有，则将下一个元素作为潜在的第 k 个元素加入优先队列中
if(t.y == matrix[0].length-1) continue;
queue.offer(new Tuple(t.x, t.y+1, matrix[t.x][t.y+1]));
}
return queue.poll().value;
}
/**
* 存储矩阵中 x，y 和该下标上对应的值的 Tuple
*/
public static class Tuple implements Comparable<Tuple>{
int x;
int y;
int value;
public Tuple(int x, int y, int value) {
this.x = x;
this.y = y;
this.value = value;
}
@Override
public int compareTo(Tuple o) {
// TODO Auto-generated method stub
return this.value – o.value;
}
}
思路二：二分法查找
二分查找的核心问题在于，如何找到查找的上界和下届。这边我们可以矩阵中的最大值和最小值作为上界和下界。然后不停的与中间值进行比较，判断当前矩阵中小于该中间值的元素有几个，如果数量不足 k，就将左指针右移，否则，就将右指针左移。直到左右指针相遇。这里需要注意，不能在数量等于 k 的时候就返回 mid 值，因为 mid 值不一定在矩阵中存在。
public int kthSmallest2(int[][] matrix, int k){
int low = matrix[0][0], high = matrix[matrix.length-1][matrix[0].length-1];
while(low <= high) {
int mid = low + (high – low) / 2;
int count = 0;
int i = matrix.length-1 , j = 0;
// 自矩阵左下角开始计算比 mid 小的数字的个数
while(i>=0 && j < matrix.length){
if(matrix[i][j]>mid) i–;
else{
count+=i+1;
j++;
}
}
if(count < k) {
low = mid + 1;
}else{
high = mid – 1;
}
}
return low;
}