| java數(shù)據(jù)結(jié)構(gòu)與算法刷題目錄（劍指Offer、LeetCode、ACM）-----主目錄-----持續(xù)更新(進(jìn)不去說明我沒寫完)：https://blog.csdn.net/grd_java/article/details/123063846 |
|---|
文章來源：http://www.zghlxwxcb.cn/news/detail-817400.html
| 解題思路 |
|---|
- 已知矩陣相對有序，可以用二分搜索，不過和一維數(shù)組排序不同，這是二維的
- 每一行都遞增，每一列也是遞增，所以每一行的最后一個(gè)元素都是當(dāng)前行最大的。每一列的最下面元素也都是當(dāng)前列最大的
- 所以，隨便劃分一個(gè)矩形區(qū)域，左上角都是最小的元素，右下角都是最大的元素。
- 此時(shí)就有了兩個(gè)邊界，讓我們來找到這個(gè)區(qū)域的最大值和最小值的中間值（不一定是矩陣中的元素）。然后判斷，矩陣中元素誰比這個(gè)中間值小。只需要判斷每行的后面的元素即可，因?yàn)槊啃羞f增排序，最后面的一定是最大的，如果最后一個(gè)比mid中間值小，那么這一行都比它小，如果倒數(shù)第2個(gè)元素比mid小，那么這一行前面的元素，一直從前往后到倒數(shù)第二個(gè)都比mid小。
| 代碼:時(shí)間復(fù)雜度O( n ? l o g 2 r ? l n*log_2{r-l} n?log2?r?l)，二分查找進(jìn)行次數(shù)為 O( l o g 2 r ? l log_2{r-l} log2?r?l)，每次操作時(shí)間復(fù)雜度為 O(n). 空間復(fù)雜度O(1) |
|---|
文章來源地址http://www.zghlxwxcb.cn/news/detail-817400.html
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int rows = matrix.length;//行數(shù)
int cols = matrix[0].length;//列數(shù)
int l = matrix[0][0];//左上角元素
int r = matrix[rows-1][cols-1];//右下角元素
while(l < r){//如果滿足"小的" 不大于 "大的"，就可以繼續(xù)循環(huán)
int mid = l + (r-l)/2;//找到他倆的中位數(shù)
int count = checkValue(matrix, mid);//獲取這個(gè)數(shù)在數(shù)組所有元素排好序后，它的相對位置
if(count < k){//如果這個(gè)數(shù)比目標(biāo)值k小，說明我們應(yīng)該在mid元素的右下區(qū)域找
l = mid+1;
} else {//否則在mid元素的左上區(qū)域找
r = mid;
}
}
return l;//最終，二分區(qū)域只剩一個(gè)元素或沒有元素
}
public int checkValue(int[][] matrix, int mid){
int r = 0;//行下標(biāo)
int c = matrix[0].length-1;//列下標(biāo)
int count = 0;//計(jì)數(shù)
while(r< matrix.length && c >= 0){//如果行下標(biāo)和列下標(biāo)不越界就繼續(xù)
if(matrix[r][c] <= mid){//如果當(dāng)前元素比mid小
r++;//行需要進(jìn)行下移，繼續(xù)判斷
count += (c+1);//既然下移了一行，那么就統(tǒng)計(jì)一行的元素，一行有c+1列，就有c+1個(gè)元素需要統(tǒng)計(jì)
//因?yàn)閿?shù)組下標(biāo)從0開始，c是當(dāng)前二分區(qū)域的最后一列的下標(biāo)，所以有c+1列
} else {//如果當(dāng)前元素比mid還大，就說明沒有我們要找的元素，讓列前移一列
c--;
}
}
return count;//最終返回有幾個(gè)元素比mid小。
}
}
到了這里，關(guān)于java數(shù)據(jù)結(jié)構(gòu)與算法刷題-----LeetCode378. 有序矩陣中第 K 小的元素的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
