閱讀403 返回首頁    go 技術社區[雲棲]

[算法係列之三十三]楊氏矩陣

即對於矩陣Table有Table[i][j] ≤Table[i][j + 1], Table[i][j] ≤ Table[i + 1][j]，我們也稱這樣的矩陣為楊氏矩陣。

給出判定某個數是否存在該矩陣中的高效算法。

 

分析：

為了便於複雜度分析，我們暫時假定該矩陣為大小n*n。如下圖所示為一個楊氏矩陣。



二分搜索解法：

許多人都觀察到了矩陣在二維上都是有序的，所以使用在每一行（或者每一列）使用二分搜索是很自然的想法。由於每一行二分搜索需要O(lgn)時間，搜索n行需要O(nlogn)的時間。顯然這個時間複雜度還是不夠高效。當然這隻是第一步嚐試，不要讓自己過早的陷入到二分搜索的泥潭中，好的方法還在後麵。

 

一種錯誤的想法：

如果不細心也許會掉入一個陷阱中。有人也許認為可以先從行來判定，如果某個數位於某2行間，則隻需要檢查相應的2列即可，這是錯誤的。如下左邊圖所示，假定我們需要查找9是否在矩陣中，由於9位於7到11之間，所以接下來在7和11的這兩列中（這2列在圖中高亮顯示）二分查找9，雖然能夠查找到9，雖然查找9成功了，但是這個方法是錯誤的。因為10也位於7到11之間，但是10並不在這2列中。

即便是如下右邊圖示查詢範圍包括2行2列，盡管在查找9和10都成功，但是還是錯誤的，反例大家可以自己找一個。

                                           

      

Step-wise線性搜索解法：

從右上角開始，每次將搜索值與右上角的值比較，如果大於右上角的值，則直接去除1行，否則，則去掉1列。如下圖顯示了查找13的軌跡。首先與右上角15比較，13<15，所以去掉最右1列，然後與11比較，這是13>11，去掉最上麵1行…以此類推，最後找到13。算法複雜度O(n)，最壞情況需要2n步，即從右上角開始查找，而要查找的目標值在左下角的時候。


【代碼】

  1. bool stepWise(int mat[][N_MAX], int N, int target,  
  2.               int &row, int &col) {  
  3.   if (target < mat[0][0] || target > mat[N-1][N-1]) return false;  
  4.   row = 0;  
  5.   col = N-1;  
  6.   while (row <= N-1 && col >= 0) {  
  7.     if (mat[row][col] < target)  
  8.       row++;  
  9.     else if (mat[row][col] > target)  
  10.       col--;  
  11.     else  
  12.       return true;  
  13.   }  
  14.   return false;  
  15. }  


四分分解算法：

通過觀察很容易發現該題可以使用分治法來解決。可以看到，矩陣的中間元素總是將矩陣分成了4個子矩陣。如下圖所示，中間元素9將矩陣分成了4個小矩陣,這4個小矩陣在行和列上麵都是排好序的，所以原問題可以分解為4個子問題。進一步觀察可以發現，每次可以排除掉1個子矩陣，也就是說隻要考慮3個子問題即可。如查找目標元素為13，則13>9，因為左上角的子矩陣都小於9，所以左上角的子矩陣可以不用再查詢，隻需要查詢剩下的3個子矩陣即可。同理，當查找元素為6時，由於6<9，因為右下角的子矩陣都大於9，因此可以直接排除右下角的子矩陣，隻需要查詢其他3個子矩陣即可。當然，如果中間元素等於查詢的目標元素，則直接返回即可，否則在剩下的3個子矩陣中查詢。


該算法代碼如下,注意邊界條件，代碼中加粗的部分不可省略，否則會導致代碼不可終止。l==r&&u==d表示矩陣中隻有一個元素，此時若不等於目標元素target，則必須返回false。

  1. bool quadPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {  
  2.   if (l > r || u > d) return false;  
  3.   if (target < mat[u][l] || target > mat[d][r]) return false;  
  4.   int col = l + (r-l)/2;  
  5.   int row = u + (d-u)/2;  
  6.   if (mat[row][col] == target) {  
  7.     targetRow = row;  
  8.     targetCol = col;  
  9.     return true;  
  10.   } else if (l == r && u == d) {  
  11.     return false;  
  12.   }  
  13.   if (mat[row][col] > target) {  
  14.     return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||  
  15.            quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||  
  16.            quadPart(mat, M, N, target, l, u, col, row, targetRow, targetCol);  
  17.   } else {  
  18.     return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||  
  19.            quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||  
  20.            quadPart(mat, M, N, target, col+1, row+1, r, d, targetRow, targetCol);  
  21.   }  
  22. }  
  23.    
  24. bool quadPart(int mat[][N_MAX], int N, int target, int &row, int &col) {  
  25.   return quadPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);  
  26. }  


該算法複雜度是多少呢？可以通過公式計算：



原文公式： T(n) = 3T(n/2) + c, 
T(n) = 3T(n/2) + c,       = 3 [ 3T(n/4) + c ] + c       = 3 [ 3 [ 3T(n/8)  + c ] + c ] + c      = 3k T(n/2k) + c (3k - 1)/2   = 3k ( T(n/2k) + c ) - c/2 Setting k = lg n,  T(n)  = 3lg n ( T(1) + c ) - c/2       = O(3lg n)       = O(nlg 3)          <== 3lg n = nlg 3       = O(n1.58) 

注：我以為這裏公式應該是T(n) = 3 * T(n/4) + c ，不對的話請大家指正。











二分算法：



這個算法我們從矩陣中間行或者中間列或者對角線開始查找，找到s滿足


 ai < s < ai+1 ,  其中ai為矩陣中的值。















a）從中間行查找，如查找10位於9到16之間。







b）從中間列查找，如查找10位於9到14之間。







c）從對角線查找，查找10位於9到17之間。



顯然不管從哪裏查找，都可以將原矩陣分成2個子矩陣，這樣就分成了2個子問題，比起四分分解法的3個子問題，這個方法應該更好。



代碼如下，注意這裏代碼確定範圍用的是線性查找，實際可以通過二分查找加速整個過程。













    

  1. 
bool binPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {  

    2. 

  2. 
  if (l > r || u > d) return false;  

    3. 

  3. 
  if (target < mat[u][l] || target > mat[d][r]) return false;  

    4. 

  4. 
  int mid = l + (r-l)/2;  

    5. 

  5. 
  int row = u;  

    6. 

  6. 
  while (row <= d && mat[row][mid] <= target) {  

    7. 

  7. 
    if (mat[row][mid] == target) {  

    8. 

  8. 
      targetRow = row;  

    9. 

  9. 
      targetCol = mid;  

    10. 

  10. 
      return true;  

    11. 

  11. 
    }  

    12. 

  12. 
    row++;  

    13. 

  13. 
  }  

    14. 

  14. 
  return binPart(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol) ||  

    15. 

  15. 
         binPart(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol);  

    16. 

  16. 
}  

    17. 

  17. 
   

    18. 

  18. 
bool binPart(int mat[][N_MAX], int N, int target, int &row, int &col) {  

    19. 

  19. 
  return binPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);  

    20. 

  20. 
}  

    21. 





該方法複雜度的分析：為了方便，假定最後查找的子矩陣為分成了2個相同大小的子矩陣,且都為原來1/4大小。






T（n) = 2T(n/4)+cn 



如果采用二分查找確定範圍，則T(n)=2T(n/4)+clgn



英文原文地址：https://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html





最後更新：2017-04-03 14:54:32
  上一篇：go android多線程下載1
  下一篇：go VB 子窗體被PictureBox控件擋住無法顯示