# Leetcode 解題速記 378. Kth Smallest Element in a Sorted Matrix
###### tags: `LeetCode` `C++`
題敘:
---
Given an `n x n matrix` where each of the rows and columns is sorted in ascending order, return the `kth` smallest element in the matrix.

Note that it is the `kth` smallest element in the sorted order, not the `kth` distinct element.

You must find a solution with a memory complexity better than `O(n^2)`.

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

測資範圍:
---
* `n == matrix.length == matrix[i].length`
* `1 <= n <= 300`
* `-109 <= matrix[i][j] <= 109`
* `All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.`
* `1 <= k <= n2`

解題筆記:
---
### 1. Binary Search
此題binary search的目標直接是答案本身。

首先，設定lower bound為`matrix[0][0]`，upper bound為`matrix.back().back()`，middle為`floor(Upper+lower)/2`。目標是統計matrix中有多少數字少於middle，計為count，當count < k時將lower bound提升到middle + 1，反之降低upper bound為middle。

如何取得count的數量呢?根據題目敘述，我們可以知道matrix中的元素以遞增的方式排序。根據這個特性，我們先找到小於M的`matrix[i][j]`，此時我們知道有j個數字小於M，因此對於i+1排我們也知道最少有j個數字小於M。因此，我們可以直接從matrix[i+1][j]開始，不用從頭開始計算，由此節省計算時間。
### 2. Priority Queue
對於這種需要排序且找特定位置元素的題目，使用priority queue也是不錯的選擇，解法相對binary search也單純許多。

我們利用priority queue會自動將元素由大到小排序的特性，只需要將matrix中的數字一一push進去，然後將priority queue的大小限制在題目要求的k個元素，只要超過k就pop掉目前最大的元素。

之後只要將整個matrix都traverse過一次後就可以在priority queue中保留k個由大到小的數字，此時queue中最大的元素便是我們題目要求的答案。

程式碼:
---
### 1. Binary Search

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
         int length = matrix.size(), lower = matrix[0][0], upper = matrix.back().back(), middle, lessThan;
         while (lower < upper)
         {
             middle = (lower + upper) >> 1;
             lessThan = 0;
             for (int i = 0, j = length - 1; i < length; ++i)
             {
                 while (j >= 0 && middle < matrix[i][j])
                     --j;
                 lessThan += j + 1;
             }
             if (lessThan < k)
                 lower = middle + 1;
             else
                 upper = middle;
         }
         return lower;
    }
};

### 2. Priority Queue

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
         priority_queue<int> pq;
        int n = matrix.size();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                pq.push(matrix[i][j]);
                if (pq.size() > k)
                {
                    pq.pop();
                }
            }
        }
        return pq.top();
    }
};