文章目錄

• 1題目理解
• 2 思路分析
• • 2.1二分思路
  • 2.2計算小于等于middle值的個數
• 3 拓展解決leetcode 668

1題目理解

輸入：一個nxn的矩陣，每一行從左到右按照升序排列，每一列從上到下按照升序排列。一個整數k。
輸出：這個矩陣中第k小的數。
規則：矩陣中數字可能重復，輸出結果，應該排序后的第k個數。

例如
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8
結果13

2 思路分析

來源于力扣官方分析，網址。
輸入矩陣matrix，每一行可以看做是一個排序好的數組，可以將這幾個小數組排序好之后取第k個數，即可。排序幾個已經排序好的數組，可以參考leetcode23。時間復雜度O(klogn)。

因為同時每一列也是排序號的，考慮用二分查找實現。

2.1二分思路

返回值一定在matrix[0][0]到matrix[n-1][n-1]之間。令函數g(x)={matrix中小于等于x的數量}={#of(matrix[i][j]<=x)}。
g(x)是一個遞增的函數，x越大，g(x)越大。
返回值是滿足g(x)>=k，的最小值。
套用模板。

class Solution {public int kthSmallest(int[][] matrix, int k) {int n = matrix.length;int l = matrix[0][0];int r = matrix[n-1][n-1];while(l<=r){int middle = l + ((r-l)>>1);if(countSmallerOrEqual(matrix,middle,n)>=k){r = middle - 1;}else{l = middle + 1;}}return l;} }

2.2計算小于等于middle值的個數

接下來的問題是如何數出$<=middle$的數量。
可以發現一個性質：任取一個數 midmid 滿足 $l\le mid\le r$，那么矩陣中不大于 mid 的數，肯定全部分布在矩陣的左上角。

例如下圖，取 mid=8：

從圖中可以看到大于middle與小于等于middle的數被一條鋸齒形狀分成了2部分 。
我們可以從左下角開始遍歷。

private int countSmallerOrEqual(int[][] matrix, int middle, int n){int i = n - 1;int j = 0;int num = 0;while(i>=0 && j<n){if(matrix[i][j]<=middle){num += i+1;j++;}else{i--;}}return num;}

時間復雜度O(nlog(r?l))。二分查找進行次數為$O(log(r?l))$，每次操作時間復雜度為 O(n)。

當然我們也可以每次遍歷一個子數組，二分查找個數。

private int countSmallerOrEqual(int[][] matrix, int middle, int n){int num = 0;for(int i = 0;i<n;i++){int l = 0, r = n-1;while(l<=r){int m = l + ((r-l)>>1);if(matrix[i][m]>middle){r = m - 1;}else{l = m + 1;}}if(l>=0){num += l;}} return num;}

3 拓展解決leetcode 668

leetocde 668 Kth Smallest Number in Multiplication Table 與本題目非常類似。
每個人都知道乘法表。輸入整數m，n表示m行n列的乘法表。在這個乘法表中找到第k小元素。
例如
Input: m = 3, n = 3, k = 5
Output: 3
Explanation:
乘法表是這樣的:
1 2 3
2 4 6
3 6 9

The 5-th 小元素是 3 (1, 2, 2, 3, 3).

參考網址

這個乘法表與上面題目中的矩陣具有相同的性質：每一行，每一列都是有序的。同樣也是要查找第k小元素，同樣矩陣中是有重復元素的。把上面代碼框架抄寫一下。

class Solution {public int findKthNumber(int m, int n, int k) {int l = 1;int r = m*n;while(l<=r){int middle = l + ((r-l)>>1);if(countSmallerOrEqual(m,n,middle)>=k){r = middle - 1;}else{l = middle + 1;}}return l;}}

不同的地方是上提的矩陣是確定的，已經生成好的，而本題需要自己生成矩陣。
題目要求m， n 的范圍是[1, 30000]，如果生成矩陣可能會引起內存不足。
當我們要計算有多少個數小于等于middle的時候，是不是可以不生成矩陣呢？

例如 m=3，n=3，middle=5，查找這個矩陣中有多少個值小于等于5。
對于第3行，是從1到3，依次乘以3，5/3=1，有1個元素小于等于5。
對于第2行，是從1到3，依次乘以2，5/2=2，有2個元素小于等于5。
對于第1行，是從1到3，依次乘以1，5/1=5，但是n=3 ，所以有3個元素小于等于5。
總小于等于5元素個數是1+2+3=6。由此可以看出，不需要生成矩陣，也可以計算。

private int countSmallerOrEqual(int m,int n,int middle){int num = 0;for(int i=1;i<=m;i++){num += Math.min(middle/i,n);}return num;}

總結

以上是生活随笔為你收集整理的378. Kth Smallest Element in a Sorted Matrix的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。