題目鏈接
有序矩陣中第 K 小的元素文章來源：http://www.zghlxwxcb.cn/news/detail-808094.html
題目描述
文章來源地址http://www.zghlxwxcb.cn/news/detail-808094.html
注意點(diǎn)
- 每行和每列元素均按升序排序
- 找到一個(gè)內(nèi)存復(fù)雜度優(yōu)于 O(n2) 的解決方案
解答思路
- 使用二分查找，思路為：
（1）因?yàn)樽笊辖堑脑刂蹈?，右下角的元素值更大，先將left設(shè)置為左上角元素的值，right設(shè)置為右下角元素的值；
（2）判斷不大于left和right中間值mid的元素?cái)?shù)量sum；
（3）如果sum小于k，則將left設(shè)置為mid + 1，否則將right設(shè)置為mid。 - 不斷重復(fù)上述過程，直到滿足sum等于k時(shí)right的最小值，此時(shí)left等于right，且right是大于等于矩陣中K個(gè)元素的臨界點(diǎn)，所以矩陣中一定會(huì)有一個(gè)元素等于right（否則說明并沒有找到sum等于k時(shí)right的最小值），right也就是有序矩陣中第 K 小的元素
代碼
class Solution {
int n;
public int kthSmallest(int[][] matrix, int k) {
n = matrix.length;
int left = matrix[0][0];
int right = matrix[n - 1][n - 1];
while (left < right) {
int mid = left + (right - left) / 2;
int sum = countLessThanMid(matrix, mid);
if (sum < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public int countLessThanMid(int[][] matrix, int mid) {
int sum = 0;
for (int i = 0; i < n; i++) {
// 如果左上角都大于mid，則一定沒有小于等于mid的元素存在
if (matrix[i][0] > mid) {
return sum;
}
// 如果右上角都小于等于mid，則該行所有元素都小于等于mid
if (matrix[i][n - 1] <= mid) {
sum += n;
continue;
}
// 其余情況查找改行小于等于mid的元素
for (int j = 0; j < n; j++) {
if (matrix[i][j] > mid) {
break;
}
sum++;
}
}
return sum;
}
}
關(guān)鍵點(diǎn)
- 二分查找的思路
- 怎么找到sum等于k時(shí)right的最小值
- 當(dāng)right - left=1，且兩個(gè)數(shù)都是負(fù)數(shù)的時(shí)候，求mid時(shí)會(huì)等于right的值，此時(shí)如果sum >= k，則會(huì)一直卡在循環(huán)中無法跳出，需要保證這種特殊情況求mid也是left，所以求mid時(shí)使用left + (right - left) / 2
到了這里，關(guān)于有序矩陣中第 K 小的元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
