Title

給定一個 n x n 矩陣，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。
請注意，它是排序后的第 k 小元素，而不是第 k 個不同的元素。

示例：

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

返回 13。

提示：

你可以假設 k 的值永遠是有效的，1 ≤ k ≤ n2 。

直接排序

Solve

最直接的做法是將這個二維數組另存為一維數組，并對該一維數組進行排序，最后返回這各一維數組中的第k個元素即為答案。

Code

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:rec = sorted(sum(matrix, []))return rec[k - 1]

復雜度分析

時間復雜度：O(n²logn)，對 n² 個數排序。

空間復雜度：O(n²)，一維數組需要存儲這 n² 個數。

二分查找

Solve

由題目給出的性質可知，這個矩陣內的元素是從左上到右下遞增的，由此可知整個二維數組中 matrix[0][0] 為最小值，matrix[n?1][n?1] 為最大值，現在我們將其分別記作 l 和 r。

可以發現一個性質：任取一個數 mid 滿足 l ≤ mid ≤ r，那么矩陣中不大于 mid 的數，肯定全部分布在矩陣的左上角。

矩陣中大于 mid 的數就和不大于 mid 的數分別形成了兩個板塊，沿著一條鋸齒線將這個矩形分開，其中左上角板塊的大小即為矩陣中不大于 mid 的數的數量。

定義一種走法：

初始位置在 matrix[n?1][0]（即左下角）；

設當前位置為 matrix[i][j]。若 matrix[i][j]≤mid，則將當前所在列的不大于 mid 的數的數量（即 i + 1）累加到答案中，并向右移動，否則向上移動；

不斷移動直到走出格子為止。

我們只要沿著這條鋸齒線走一遍即可計算出這兩個板塊的大小，也自然就統計出了這個矩陣中不大于 mid 的數的個數了。

我們發現這樣的走法時間復雜度為 O(n)，即我們可以線性計算對于任意一個 mid，矩陣中有多少數不小于它。這滿足了二分答案的性質。

不妨假設答案為 x，那么可以知道 l ≤ x ≤ r，這樣就確定了二分答案的上下界。

每次對于「猜測」的答案 mid，計算矩陣中有多少數不大于 mid ：

• 如果數量不多于 k，那么說明最終答案 x 不小于 mid；
• 如果數量少于 k，那么說明最終答案 x 大于 mid。

這樣我們就可以計算出最終的結果 x 了。

Code

def kthSmallest_binarySearch(self, matrix: List[List[int]], k: int) -> int:def check(middle):i, j, num = length - 1, 0, 0while i >= 0 and j < length:if matrix[i][j] <= middle:num += i + 1j += 1else:i -= 1return num >= klength, left, right = len(matrix), matrix[0][0], matrix[-1][-1]while left < right:mid = (left + right) // 2if check(mid):right = midelse:left = mid + 1return left

復雜度分析

時間復雜度：O(nlog(r?l))，二分查找進行次數為 O(log(r?l))，每次操作時間復雜度為 O(n)。

空間復雜度：O(1)。

總結

以上是生活随笔為你收集整理的378. Kth Smallest Element in a Sorted Matrix 有序矩阵中第K小的元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。