每天一道leetcode378-有序矩陣中第K小的元素
- 2019 年 10 月 4 日
- 筆記
題目
leetcode378-有序矩陣中第K小的元素
英文鏈接：
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
中文鏈接：
https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/
分類：二分查找類
題目詳述
給定一個 n x n 矩陣，其中每行和每列元素均按升序排序，找到矩陣中第k小的元素。 請注意，它是排序後的第k小元素，而不是第k個元素。
示例:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,返回 13。
說明: 你可以假設 k 的值永遠是有效的, 1 ≤ k ≤ n2 。
暴力解決
思路
- 額，看到這個題目，一開始大體思路就是暴力解決；
- 遍歷整個二維數組，然後把這個二維數組存到一個一維數組中，然後對這個一維數組，進行排序，然後取這個一維數組第k個值就行。
程式碼
class Solution { public int kthSmallest(int[][] matrix, int k) { if(matrix.length == 0 || matrix[0].length == 0) return -1; int rows = matrix.length; int cols = matrix[0].length; int number = rows * cols; int [] list = new int[number]; int count = 0; for(int i=0;i<rows;i++) { for(int j=0;j<cols;j++) { list[count] = matrix[i][j]; count++; } } Arrays.sort(list); return list[k-1]; } }
二分解決
思路
- 由於是一個矩陣，左上角的數是最小值，右下角的數是最大值，所以可以利用這一個特點來進行二分，每次取兩個邊界的值進行除以2，得到一個mid值；
- 然後根據這個mid值，統計整個矩陣中，小於mid值的個數，如果小於mid的值的個數剛好大於等於k個，那麼說明應該縮小right的值到mid,如果小於k個，那麼說明left應該變成mid；
- 這樣一步步進行緊逼，找到最後的這個數據。
程式碼
class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; int left = matrix[0][0], right = matrix[n - 1][n - 1]; while (left + 1 < right) { int mid = (right - left) / 2 + left; int num = count(matrix, mid); if (num >= k) { right = mid; } else { left = mid; } } if (count(matrix, right) <= k - 1) return right; return left; } public int count(int[][] matrix, int target) { int n = matrix.length; int i = n - 1, j = 0; int res = 0; while (i >= 0 && j < n) { if (matrix[i][j] < target) { res += i + 1; //index + 1 = number of elements. j++; } else { i--; } } return res; } }
程式碼講解
- 17行到30行程式碼就是求矩陣中小於target的數的大小，這裡的話從第0列開始的最底層開始找，如果左下角的數比target小，那麼說明這一列的數都是小於target所以，也就是出現了程式碼22行到24行，因為這個一列已經找過了，所以j++，移動到下一列去找；
- 如果左下角的數比target大，由於每一行遞增，所以只能是i–,來去找下一行；以上就是對17行-30行程式碼的講解
- 題目中使用了二分查找，去找最小值和最大值的中間值，如果小於中間值的個數是k個或者大於k個，那麼讓right去等於mid，往左邊逼近；
- 如果小於中間值mid的個數是小於k的，那麼說明不夠k個，也就只能取把left變大，等於mid;
- 然後循環結束的條件是left+1<right;說明這時候結束的時候已經是left與right無限逼近了，這個時候left與right的中間值在數組裡面（這裡我也沒有數學證明，left與right一直求中間值，那麼最後中間值mid一定在數組裡面？？？這個我自己試驗了幾個數組，確實是這樣子，但是我數學能力有限，無法去證明，有人能證明嗎，歡迎評論區留言）
結束語
2018.11.1打卡~
END
