相关题解:y总题解
这是值域二分
,不是索引二分
。
- 索引二分:
求i
, 比如数组nums 长度为n,索引 i~[0, n - 1], 是索引的可取值区间 i~[0, n - 1] 由题已知,根据索引处 值的性质nums[i]
将索引可取值区间 i~[0, n - 1] 进行二段性分割
。 - 值域二分:
求h
,h的可取值值域区间[l, r]
由题已知,假定 区间中的某个值 h是所求解
,那么要把区间分为[l, h]和[h+1, r]
或者[l, h-1]和[h, r]
,就要由题设计一个性质
使得 h左面的区间 和 h右面的区间 一个满足, 一个不满足,对区间进行二段性分割。- (设计的这个性质往往是 根据
另外一个
带有索引
的一维/二维数组
设计的,这里就要区分开h的值域区间[l, r]
和另外
一个带有索引的一维/二维数组 的 索引区间[0, n - 1])
。
- (设计的这个性质往往是 根据
题目
378. 有序矩阵中第 K 小的元素
思路
-
值域二分: 由题知 元素 行 和 列 都是 非递减序列,所以 元素大小范围在[l, r] = [
matrix[0][0], matrix[m-1][n-1]
]之间,也就是值域区间是已知的。假设 target ~ [l = matrix[0][0], r = matrix[m-1][n-1]
] 是 matrix 中第k 小的元素(matrix索引范围[0, n*n-1])。 -
利用行有序,列有序 的特点,从右上角 0 行 向左下角 开始遍历 进行判断(从左下角 n-1行 到右上角也可)。每一行先从右往左遍历,如果>mid,跳到左边一列 j–;如果<=mid,说明左边的数<=mid,就将此行的cnt进行计数,然后跳到下一行 i。每次判断,每次循环 不是 j–就是 i;i初始值为0,j初始值为n-1,i和j要满足的条件 i>=0 && j <=n-1。最多循环n + m - 1次,时间复杂度为O(m + n) = O(n + n) = O(2n) = O(n)
行有序
:右上角 开始遍历,从右向左 遍历每一行的时候如果遇到一个比 mid 小的数字,就不用在这一行向左 继续遍历了,因为行是升序的,左边的数都<=mid。列有序
:右上角 开始遍历,如果遇到一个数比mid大,因为列升序,所以这一列的下方从下一行到最后一行的元素都 >mid
,所以找<=mid的数时,就不用考虑这些元素。
int cnt_LessEqual_t(vector<vector<int>>& matrix, int t, int m, int n){ // 时间复杂度为O(m + n)= O(n + n) = O(2n) = O(n)
// int cnt = 0, i = 0, j = n-1;
// while (i < m && j >= 0){ // // 每一次循环,要么j--, 要么i++, 从右上角 向 左下角移动,最多循环不超过 n + m 次
int cnt = 0;
for (int i = 0, j = n-1; i < m && j >= 0; ){ // 每一次循环,要么j--, 要么i++, 从右上角 向 左下角移动,最多循环不超过 n + m 次
if (matrix[i][j] > t) j--; // 每一行先从右往左遍历,如果>mid,跳到左边一列 j--
else { // 如果<=mid,说明左边的数<=mid,就将此行的cnt进行计数,然后跳到下一行 i++
cnt += (j - 0 + 1);
i++;
}
}
return cnt;
}
代码
// 题目中 -10^9 <= matrix[i][j] <= 10^9, 10^3 < 2^10, 10^9 < 2^30, int mid = l + r >> 1 就不用考虑溢出。
// 如果 int l = INT_MIN, r = INT_MAX; 需要 int mid = (long long) l + r >> 1 防止溢出。
class Solution {
public:
// int m, n; // 把 m, n 定义为全局变量 就不用每次调用 cnt_LessEqual_t()函数时 传参m, n 或在 cnt_LessEqual_t()函数内部重新计算一遍m,n 了
// 这里使用 for 和 while的嵌套循环,表面上一看上去好像是m * n, 逻辑不清晰,所以改写为下面的只用一层for循环的写法
// int cnt_LessEqual_t(vector<vector<int>>& matrix, int t){
// int j = n - 1, cnt = 0;
// for (int i = 0; i < m; i++){
// while (j >= 0 && matrix[i][j] > t) j--;
// cnt += j + 1;
// }
// return cnt;
// }
int cnt_LessEqual_t(vector<vector<int>>& matrix, int t, int m, int n){ // 时间复杂度为O(m + n)= O(n + n) = O(2n) = O(n)
// int cnt = 0, i = 0, j = n-1;
// while (i < m && j >= 0){ // // 每一次循环,要么j--, 要么i++, 从右上角 向 左下角移动,最多循环不超过 n + m 次
int cnt = 0;
for (int i = 0, j = n-1; i < m && j >= 0; ){ // 每一次循环,要么j--, 要么i++, 从右上角 向 左下角移动,最多循环不超过 n + m 次
if (matrix[i][j] > t) j--; // 每一行先从右往左遍历,如果>mid,跳到左边一列 j--
else { // 如果<=mid,说明左边的数<=mid,就将此行的cnt进行计数,然后跳到下一行 i++
cnt += (j - 0 + 1);
i++;
}
}
return cnt;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int m = matrix.size(), n = matrix[0].size();
int l = matrix[0][0], r = matrix[m-1][n-1];
while (l < r){ // 最多循环 log(r - l + 1) 次
int mid = l + r >> 1;
int count = cnt_LessEqual_t(matrix, mid, m, n); // cnt_LessEqual_t()函数时间复杂度为O(m + n)= O(n + n) = O(2n) = O(n)
if (count >= k) r = mid; // [ans, r]满足count >= k
else l = mid + 1; // [l, ans - 1] 不满足 count >= k
}
return l;
}
};
时间复杂度
二分最多循环 log(r - l + 1) 次,记 区间长度 V = r- l + 1,cnt_LessEqual_t()函数时间复杂度为O(m + n)= O(n + n) = O(2n) = O(n),合起来就是O(n*log(V))