### 题目

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.

### 用多个指针

#### 代码

class Solution {
/** list of pointer */
public int kthSmallest(int[][] matrix, int k) {
if (matrix.length == 0) { return 0; }
if (matrix.length == 1) { return (k == 1)? matrix[0][0] : 0; }
int remain = k - 1;
Pair min = new Pair(0,0);
int minVal = matrix[0][0];
while (!list.isEmpty()) {
if (remain == 0) { return minVal; }
min = null;
minVal = Integer.MAX_VALUE;
for (Pair p : list) {
if (matrix[p.x][p.y] <= minVal) {
min = p;
minVal = matrix[p.x][p.y];
}
}
--remain;
if (min.y < (matrix.length - 1)) {
++min.y;
} else {
list.remove(min);
}
if (!list.isEmpty()) {
Pair last = list.get(list.size()-1);
if ((last.y == 1) && (last.x < (matrix.length - 1))) {
}
}
}
return (remain == 0)? minVal : 0;
}

private class Pair {
int x;
int y;
private Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}


### 二分查找

matrix = [
[ 1,  5,  9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,

return 13.


#### 代码

class Solution {
public int kthSmallest(int[][] matrix, int k) {
int size = matrix.length;
int lo = matrix[0][0];
int hi = matrix[size-1][size-1];
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int count = 0;
int cur = size - 1;
for (int i = 0; i < size; i++) { // 统计 <= mid 的数字个数
while (cur >= 0 && matrix[i][cur] > mid) { cur--; }
count += (cur + 1);
}
if (count < k) { // mid 太小
lo = mid + 1;
} else { // mid 有可能太大，有可能正好
// 当 count > k 时，不能直接判断 mid 太大， 因为存在重复的数字
hi = mid;
}
}
return lo;
}
}