給予一個n*n矩陣, 各行跟各列都已排序為由小到大的順序, 求在矩陣中第k小的數字
注意是求 當整個矩陣的所有數字排序後的第k個數字
可假設k為有效數字, 也就是 1 ≤ k ≤ n²
範例
Input: matrix = [[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]], k = 8
Output: 13.想法:
如果只是一般完全沒有排序的n*n矩陣, 那我們最快的方法就是把他們都放成一維陣列並排序後, 回傳第k個數字
這樣的時間複雜度就會是O(n²lgn²) 因為我們排序了n²個數字
然而, 我們現在的二維矩陣是已排序好了, 我們需要好好利用它各行跟各列都排序的這個優點
👉從這個特點, 也可以說現在位置的數字matrix[i][j]絕對比它右格matrix[i][j+1]以及它下面的格子matrix[i+1][j]都還來的小
而這給我們一個小提示 — 如果我們找到了第(k-1)小的數字, 那第k小的數字的所在位置一定是在所有(k-1)的數字們各右格跟下格的其中一格
所以現在的問題就是, 那我們要怎麼找到在矩陣中第k小的數字?
不難看出第1小的數字就是在最左上角(0, 0), 而第2小的數字則是會在(0,0)的右邊(0,1)或下格(1,0), 若我們找到第2小的數字在(1,0), 第3小的數字則是會在(0,1), (1,1) 跟 (2,0) 這些數字之間… 以此類推
因次我們大概知道這些的規則了, 如果我們有一個容器去裝目前遇到的所有的數字, 並一直維持著由小到大的排序, 我們會每每把最小數字取出, 並同時塞進這個目前最小數字的右格及下格, 讓這兩個數字跟 目前其他所有數字一起做為下一個最小數字的候補, 而其他還沒被裝進容器的數字我們就先不管他們, 因為他們數字太大了, 連他們的上格或左格都還沒被選上前, 他們不可能有機會與其他小數字競爭
在Java中有一個資料結構PriorityQueue可以幫助我們排序好, 並且讓我們可以用少許時間取跟塞值
而為了避免重複紀錄到同樣位置的數字, 我也另外用了一個boolean的二維陣列來記錄訪過的位置
因為我們不只需要紀錄數字的值, 我們也需要知道這個數字的取出位置來自哪裡, 因為我們在決定這個數字是"目前容器中最小數字"的時候, 把他的右格及下格都放進容器中, 因為當這個數字被選中後, 他的這兩個鄰居也才有機會一起成為候選人
因此, 我自創了一個class類別, 讓我們可以一次存數字值, 還有他的位置
以下為17ms 的程式碼, 贏過38% —
class Solution {
public int kthSmallest(int[][] matrix, int k) {
if(k==1)
return matrix[0][0];
int n = matrix.length;
PriorityQueue<Node> queue = new PriorityQueue<Node>();
boolean[][] visited = new boolean[n][n];
queue.offer(new Node(0,0,matrix[0][0]));
visited[0][0] = true;
while(!queue.isEmpty())
{
Node cur = queue.poll();
k--;
if(k==0)
return cur.val;
int i = cur.i, j = cur.j;
if(i!=n-1 && !visited[i+1][j])
{
queue.offer(new Node(i+1,j,matrix[i+1][j]));
visited[i+1][j] = true;
}
if(j!=n-1 && !visited[i][j+1])
{
queue.offer(new Node(i,j+1,matrix[i][j+1]));
visited[i][j+1] = true;
}
}
return -1;
}
}
class Node implements Comparable<Node>{
int i;
int j;
int val;
public Node(int i,int j,int val){
this.i = i;
this.j = j;
this.val = val;
}
@Override
public int compareTo(Node n){
return this.val - n.val;
}
}時間複雜度為 O(n²lgn²), 因為我們使用的是 PriorityQueue, 每次從n²大小的queue中放或取Node都需要花O(lgn²)
那我們有沒有辦法能更有效率地找到在陣列排名第k的數字?
因為我們通常在一個排序的陣列想要找特定數字的時候, 我們可以用二元搜索法, 只靠O(lgn)的時間找到目標數字, 那我們可不可以也在這個排序好的矩陣中找到我們要的目標?
程式邏輯:
答案是可以, 我們將會在程式中的兩個不同地方皆使用二元搜索法,來幫我們加速找到矩陣中排名第k的數字
因為我們在這個矩陣的最小數字是matrix[0][0], 最大數字是matrix[n-1][n-1], 因此我們也可以做結論 — 所有數字皆會在這個[matrix[0][0], matrix[n-1][n-1]]範圍中
在每次的循環中, 我們都會一直抓 現在範圍的起點和終點 (假設一開始範圍在[start, end]) 的平均值, 並使用helper method來找平均數字mid在矩陣中的排名:
- 若mid在矩陣中的排名小於k, 代表矩陣中排名第k的數字比這個平均數字還大, 也代表我們想要找的數字其實應該在這個範圍中: [ mid+1, end]
- 若mid在矩陣中的排名大於或等於k, 代表矩陣中排名第k的數字比mid還小, 我們想看我們能不能再下修這個mid, 因此我們會把範圍縮為 [start,mid]
我們只有在當我們現在範圍中只剩一個數字的時候, 才會停止呼叫helper method來找 範圍起點及終點的平均數 在矩陣中的排名
你可能會疑惑, 當我們是用範圍而非用位置(i, j)來做二元搜索的時候, 有沒有可能我們正在找 根本不在矩陣中數字的排名?
是的, 我們真的可能大部分的時間都在找不存在矩陣裡面的數字 在矩陣中的排名
若我們真的每次一當我們找到某數字是排名k的話就回傳這個數字, 這樣的演算法就會是錯的, 我們可能會回傳一個根本不在矩陣裡面的數字回去
但我們的回傳條件是當我們一直上修又下修第k數字的範圍, 直到範圍剩一個數字, 因此我們是很確定這個數字在矩陣裡面後, 才會回傳
👷來用例子看我們怎麼用縮減範圍來找到矩陣中排名第21的數字:
原本想用上述都用過的陣列來當例子, 但為了可以更顯著的看到我們如何修減範圍, 我將最後兩格改放兩個超大的數字:
🔧Step 1. 一開始我們的範圍為 [1, 1000], 我們將呼叫helper method來找平均數500在矩陣中的排名, 得知500大於矩陣中24個數字
24大於目標排名21, 因此我們可以把範圍往下縮到[1, 500]
🔧Step 2. 現在範圍[1,500], 利用helper method得知其平均250的排名亦為24, 再次下縮範圍 [1, 250]
🔧Step 3. 現在範圍[1,250], 利用helper method得知其平均125的排名亦為24, 再次下縮範圍 [1, 125]
🔧Step 4. 現在範圍[1,125], 利用helper method得知其平均63的排名為23, 再次下縮範圍 [1, 63]
🔧Step 5. 現在範圍[1,63], 利用helper method得知其平均32的排名為16, 發現我們找過頭了, 但也得知目標排名數字會在[33, 63]
🔧Step 6. 現在範圍[33,63], 利用helper method得知其平均48的排名為22, 再次下縮範圍 [33, 48]
🔧Step 7. 現在範圍[33,48], 利用helper method得知其平均40的排名為21, 是目標排名! 但是現在我們不能確定40存在於矩陣中, 此時只能繼續下縮範圍 [33, 40]
🔧Step 8. 現在範圍[33,40], 利用helper method得知其平均36的排名為18, 發現我們找過頭了, 但也得知目標排名數字會在[37, 40]
🔧Step 9. 現在範圍[37,40], 利用helper method得知其平均38的排名為18, 發現我們找過頭了, 但也得知目標排名數字會在[39, 40]
🔧Step 10. 現在範圍[39,40], 利用helper method得知其平均39的排名為19, 發現我們找過頭了, 但也得知目標排名數字會在[40, 40]
🚧而現在範圍只剩下一個數字, 因此我們也才能確定40就是答案並回傳回去
既然現在知道了主要邏輯, 那我們來看helper method如何用O(n)來找到給予數字在矩陣中的排名
強力推薦大家先看過我寫的這篇Leetcode — 240. Search a 2D Matrix II (中文)來了解我們怎麼用二元搜索來在矩陣中找目標數字, 因為問題240的矩陣跟我們這題的矩陣條件一模一樣, 只要花O(2n)時間就可以找到目標
讀完Leetcode — 240. Search a 2D Matrix II (中文), 你應該會知道為何我們選擇從矩陣左下角開始走訪整個矩陣, 我們將直接沿用我們在問題240的程式邏輯, 不過這次我們並不只是要找到數字有無存在在矩陣中, 我們還必須同時去數總共有多少數字小於等於目標數字
因為我們已在上述文章詳細講解我們如何在矩陣中找目標數字了, 我將會用一個例子來帶過我們如何在找數字的途中順便計算有幾個小於等於目標數字的數字
👷以下為我們將用的範例矩陣, 假設我們現在要數在矩陣中有多少數字小於等於20
⚠️我們將用變數count 來代表我們目前找到多少數字是小於等於20.
🔧Step 1. 我們現在的位置的數字matrix[4][0] ≤ 20, 因為我們在最後一列, 代表所有在這一直行的數字都同樣小於等於目標數字.
我們也將會為了找大一點的數字往右移, 希望找到目標數字20
💭count = 5
🔧Step 2. 我們現在的位置的數字matrix[4][1] > 20, 我們為了找到小一點的數字, 因此往上走
💭count = 5
🔧Step 3. 我們現在的位置的數字matrix[3][1] > 20, 我們為了找到小一點的數字, 因此往上走
💭count = 5
🔧Step 4. 我們現在的位置的數字matrix[2][1] > 20, 我們為了找到小一點的數字, 因此往上走
💭count = 5
🔧Step 5. 我們現在的位置的數字matrix[1][1] ≤ 20, 代表包含這格及這格正上方的同行數字都同樣小於等於目標數字, 我們也將會為了找大一點的數字往右移
💭count = 5 + 2 = 7
🔧Step 6. 我們現在的位置的數字matrix[1][2] > 20, 我們為了找到小一點的數字, 因此往上走
💭count = 7
🔧Step 7. 我們現在的位置的數字matrix[0][2] ≤ 20, 代表包含這格及這格正上方的同行數字都同樣小於等於目標數字, 我們也將會為了找大一點的數字往右移
💭count = 7 + 1 = 8
🔧Step 8. 我們現在的位置的數字matrix[0][3] ≤ 20, 代表包含這格及這格正上方的同行數字都同樣小於等於目標數字, 我們也將會為了找大一點的數字往右移
💭count = 8+ 1 = 9
🔧Step 9. 我們現在的位置的數字matrix[0][4] > 20, 我們為了找到小一點的數字, 因此往上走
💭count = 9
🚧我們已無路可走, 因此我們已找完所有小於等於20的數字了
總共有9個數字≤20, 而若我們把所有達成條件的格子都標示成紅色, 則會如下圖所示 —
我們可以看到其實這些格子被我們走訪過的路徑包圍
以下為0ms程式碼 贏過 100% —
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int start = matrix[0][0];
int end = matrix[n-1][n-1];
while(start < end)
{
int mid = start + (end - start)/2;
int rank = helper(matrix, mid);
if(rank < k)
start = mid + 1;
else
end = mid;
}
return start;
}
//count how many numbers <= target
private int helper(int[][] matrix, int target){
int n = matrix.length;
int i = n-1, j = 0, count = 0;
while(i >= 0 && j < n)
{
if(matrix[i][j] <= target)
{
count += (i+1);
j++;
}
else
i--;
}
return count;
}時間複雜度是 O(n*lg(max-min)) , max跟min就代表矩陣中的最大數和最小數, 因為我們利用這個範圍數字來做二元搜索法, 因此時間複雜度就會是O(lg(範圍長度))
而每次我們都會呼叫helper method來幫我們找 現在範圍起點終點的平均數的排名, 因此最後時間複雜度就是兩者相乘
