# 0378. Kth Smallest Element in a Sorted Matrix
###### tags: `Leetcode` `FaceBook` `Medium` `Merge Sorted List` `Binary Search`
Link: https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
## 思路
### 思路一 Priority Queue $X=MIN(K,N)$ $O(X+KlogX)$ $O(X)$
x是heap的最大size，N是matrix的长度，建heap需要O(X)，然后一共拿K次最小值，每次O(logX)
跟[0023. Merge k Sorted Lists](https://hackmd.io/SgY_aFxoRHurr9S9W_OI9A)有点像
用一个priority queue，存每个array里面最小的值，如果被pop，就换下一个
### 思路二 Binary Search $O(Nlog(maxVal-minVal))$ N是col数+row数
binary search最重要的是确定搜索范围
有两种搜索范围：index和range
Most usually, when the array is sorted in one direction, we can use index as "search space", when the array is unsorted and we are going to find a specific number, we can use "range".
two examples of these two "search space"
1. [index](https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/) ( the array is sorted)
2. [range](https://leetcode.com/problems/find-the-duplicate-number/) (Unsorted Array)

这个方法有三个很重要的地方
- 由于column也是排过序的，所以在找count的时候，只需要O(N)，原因是从第一行开始找，如果对于idx j，matrix[i][j]>mid，那么matrix[i+1][j]也一定大于mid，所以在跑i的回圈的时候（一共跑了matrix.length次）j最多会移动matrix[0].length次，因此时间复杂度为O(N)
- 之前写mid是用 ```int mid = (start+end)/2```，在没有overflow的情况下，通常都是正确的，mid永远都靠近start，但这道题就不对，原因是，这道题有负数测资，例如start=-5, end=-4的时候mid就会等于-4，靠近end，而不是靠近start，就会进入无穷回圈，解决方法就是**无论什么题都写```int mid = start+(end-start)/2```**
- 为什么左边界lo一定在matrix里面，因为binary search找到的值，一定是让count=k的第一个值，既然这个值可以让count从k-1变成k，那么它一定在matrix里面
## Code
### 思路一

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        Queue<Pair<Integer, Integer>> pq = new PriorityQueue<>((a,b)->(matrix[a.getKey()][a.getValue()] - matrix[b.getKey()][b.getValue()]));
        for(int i = 0;i < Math.min(matrix.length,k);i++){
            pq.add(new Pair<>(i,0));
        }
        for(int i = 0;i < k-1;i++){
            Pair<Integer,Integer> small = pq.poll();
            if(small.getValue()+1<matrix[small.getKey()].length){
                pq.add(new Pair<>(small.getKey(), small.getValue()+1));
            }
        }
        return matrix[pq.peek().getKey()][pq.peek().getValue()];
    }
}

### 思路二

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int lo = matrix[0][0], hi = matrix[matrix.length - 1][matrix[0].length - 1] + 1;
        while(lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0,  j = matrix[0].length - 1;
            for(int i = 0; i < matrix.length; i++) {
                while(j >= 0 && matrix[i][j] > mid) j--;
                count += (j + 1);
            }
            if(count < k) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}