作者推薦

視頻算法專題

本文涉及的基礎知識點

二分查找算法合集

LeetCode378. 有序矩陣中第 K 小的元素

給你一個 n x n 矩陣 matrix ，其中每行和每列元素均按升序排序，找到矩陣中第 k 小的元素。
請注意，它是 排序后 的第 k 小元素，而不是第 k 個 不同 的元素。
示例 1：
輸入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
輸出：13
解釋：矩陣中的元素為 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：
輸入：matrix = [[-5]], k = 1
輸出：-5
提示：
n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
題目數據 保證 matrix 中的所有行和列都按 非遞減順序 排列
1 <= k <= n2

二分查找

Cnt(x)函數，計算小于等于x的個數。如果Cnt(x)小于k，則x一定不是第k小的元素。Cnt(x) >= k，且x最小。由于是找第一個符合的，故用左開右閉空間。

Cnt(x)

容易想到的方法是：各行分別二分查找，時間復雜度是: O(nlogn)。
時間復雜度O(n)的做法是：
對倒數第一行暴力查找，使得mat[0][0,…r) 全部小于等于x，mat[0][r]不存在或大于x。
從r開始，對倒數第二行到倒數第n行分別暴力查找。
由于r不復位，所以r最多從0到n，故時間復雜度是O(n)，不是O(n2)。

代碼

class Solution {
public:int kthSmallest(vector<vector<int>>& matrix, int k) {m_c = matrix.size();int left = matrix.front().front()-1, r = matrix.back().back();while (r - left > 1){const auto mid = left + (r - left) / 2;if (Cnt(matrix, mid) >= k){r = mid;}else{left = mid;}}return r;}int Cnt(const vector<vector<int>>& matrix, int x){int iCnt = 0;for (int r = m_c - 1,right=0; r >= 0; r--){for (; (right < m_c) && (matrix[r][right] <= x); right++);iCnt += right;}return iCnt;}int m_c;
};# 測試用例```cpp
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<vector<int>> matrix;int k;{Solution slu;matrix = { {1,5,9},{10,11,13},{12,13,15} }, k = 8;auto res = slu.kthSmallest(matrix, k);Assert(13, res);}{Solution slu;matrix = { {-5} }, k = 1;auto res = slu.kthSmallest(matrix, k);Assert(-5, res);}
}

擴展閱讀

視頻課程

有效學習：明確的目標 及時的反饋 拉伸區（難度合適），可以先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成戰斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176

相關下載

想高屋建瓴的學習算法，請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想對大家說的話
聞缺陷則喜是一個美好的愿望，早發現問題，早修改問題，給老板節約錢。
子墨子言之：事無終始，無務多業。也就是我們常說的專業的人做專業的事。
如果程序是一條龍，那算法就是他的是睛

測試環境

操作系統：win7 開發環境： VS2019 C++17
或者 操作系統：win10 開發環境： VS2022 C++17
如無特殊說明，本算法用**C++**實現。