題目鏈接

有序矩陣中第 K 小的元素

題目描述

注意點(diǎn)

• 每行和每列元素均按升序排序
• 找到一個(gè)內(nèi)存復(fù)雜度優(yōu)于 O(n2) 的解決方案

解答思路

• 使用二分查找，思路為：
  （1）因?yàn)樽笊辖堑脑刂蹈?#xff0c;右下角的元素值更大，先將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，則該行所有元素都小于等于midif (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