[LeetCode] Kth Smallest Element in a Sorted Matrix 有序矩陣中第K小的元素

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:

Note: 

You may assume k is always valid, 1 ≤ k ≤ n2.

這道題讓我們求有序矩陣中第K小的元素，這道題的難點在于數組并不是蛇形有序的，意思是目前行的最後一個元素并不一定會小于下一行的首元素，是以我們并不能直接定位第K小的元素，是以隻能另辟蹊徑。先來看一種利用堆的方法，我們使用一個最大堆，然後周遊數組每一個元素，将其加入堆，根據最大堆的性質，大的元素會排到最前面，然後我們看目前堆中的元素個數是否大于k，大于的話就将首元素去掉，循環結束後我們傳回堆中的首元素即為所求:

解法一：

這題我們也可以用二分查找法來做，我們由于是有序矩陣，那麼左上角的數字一定是最小的，而右下角的數字一定是最大的，是以這個是我們搜尋的範圍，然後我們算出中間數字mid，由于矩陣中不同行之間的元素并不是嚴格有序的，是以我們要在每一行都查找一下mid，我們使用upper_bound，這個函數是查找第一個大于目标數的元素，如果目标數在比該行的尾元素大，則upper_bound傳回該行元素的個數，如果目标數比該行首元素小，則upper_bound傳回0, 我們周遊完所有的行可以找出中間數是第幾小的數，然後k比較，進行二分查找，本解法的整體時間複雜度為O(nlgn*lgX)，其中X為最大值和最小值的內插補點，參見代碼如下：

解法二：

上面的解法還可以進一步優化到O(nlgX)，其中X為最大值和最小值的內插補點，我們并不用對每一行都做二分搜尋法，我們注意到每列也是有序的，我們可以利用這個性質，從數組的左下角開始查找，如果比目标值小，我們就向右移一位，而且我們知道目前列的目前位置的上面所有的數字都小于目标值，那麼cnt += i+1，反之則向上移一位，這樣我們也能算出cnt的值。其餘部分跟上面的方法相同，參見代碼如下：

解法三：