### 题目

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.

### 计算所有可能的配对

#### 代码

/**
* x = min(m*n, k)
* O(xlogx)
* 老老实实计算出每一对和，放进一个Heap里输出。
*/
class Solution1 implements Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> res = new ArrayList<>();
if (nums1 == null || nums2 == null || k < 0) {
return res;
}
PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
return a[0] + a[1] - b[0] - b[1];
}
});
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
heap.offer(new int[]{nums1[i], nums2[j]});
}
}
for (int i = 0; i < k && !heap.isEmpty(); i++) {
}
return res;
}
}


### 用Heap维护一组指针，O(klog(min(m,n)))

nums1[x] + nums2[y] <= nums1[x] + nums2[y+1]

nums1[x] + nums2[0] <= nums1[x+1] + nums2[0]

#### 代码

class Solution {
public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<int[]> res = new ArrayList<>();
if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0 || k <= 0) {
return res;
}
// 以较小的数组作为生成向量的主数组
int[] numsA = (nums1.length <= nums2.length)? nums1 : nums2;
int[] numsB = (numsA == nums1)? nums2 : nums1;
PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>(){
public int compare(int[] a, int[] b) {
return numsA[a[0]] + numsB[a[1]] - numsA[b[0]] - numsB[b[1]];
}
});
int vectorP = 0;
heap.offer(new int[]{vectorP, 0});
while (k-- > 0 && !heap.isEmpty()) {
int[] next = heap.poll();
if (numsA == nums1) {
} else {
}
if (next[0] == vectorP && vectorP < numsA.length - 1 && next[1] == 0) { // 添加新向量
heap.offer(new int[]{++vectorP, 0});
}
if (next[1] < numsB.length - 1) { // 弹出的向量向前进一格
heap.offer(new int[]{next[0], next[1] + 1});
}
}
return res;
}
}


### 一种可能的O(k)的解法

Stephanpochmann又给出了一种O(k)的解法。基本思想基于kth smallest element in a sorted matrix这个子问题，