[算法系列之三十三]杨氏矩阵

末蓝、 2023-06-25 04:54 17阅读 0赞

![20131128230328468][]

即对于矩阵Table有Table\[i\]\[j\] ≤Table\[i\]\[j + 1\], Table\[i\]\[j\] ≤ Table\[i + 1\]\[j\]，我们也称这样的矩阵为杨氏矩阵。

给出判定某个数是否存在该矩阵中的高效算法。

**分析：**

为了便于复杂度分析，我们暂时假定该矩阵为大小n\*n。如下图所示为一个杨氏矩阵。

![format_png][]

**二分搜索解法：**

许多人都观察到了矩阵在二维上都是有序的，所以使用在每一行（或者每一列）使用二分搜索是很自然的想法。由于每一行二分搜索需要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都成功，但是还是错误的，反例大家可以自己找一个。

![format_png 1][]                                        ![format_png 2][]

**Step-wise线性搜索解法：**

从右上角开始，每次将搜索值与右上角的值比较，如果大于右上角的值，则直接去除1行，否则，则去掉1列。如下图显示了查找13的轨迹。首先与右上角15比较，13<15，所以去掉最右1列，然后与11比较，这是13>11，去掉最上面1行…以此类推，最后找到13。算法复杂度O(n)，最坏情况需要2n步，即从右上角开始查找，而要查找的目标值在左下角的时候。

![format_png 3][]

【代码】

bool stepWise(int mat[][N_MAX], int N, int target,  
                  int &row, int &col) {  
      if (target < mat[0][0] || target > mat[N-1][N-1]) return false;  
      row = 0;  
      col = N-1;  
      while (row <= N-1 && col >= 0) {  
        if (mat[row][col] < target)  
          row++;  
        else if (mat[row][col] > target)  
          col--;  
        else  
          return true;  
      }  
      return false;  
    }

**四分分解算法：**

通过观察很容易发现该题可以使用分治法来解决。可以看到，矩阵的中间元素总是将矩阵分成了4个子矩阵。如下图所示，中间元素9将矩阵分成了4个小矩阵,这4个小矩阵在行和列上面都是排好序的，所以原问题可以分解为4个子问题。**进一步观察可以发现，每次可以排除掉1个子矩阵，也就是说只要考虑3个子问题即可。**如查找目标元素为13，则13>9，因为**左上角的子矩阵都小于9，所以左上角的子矩阵可以不用再查询**，只需要查询剩下的3个子矩阵即可。同理，当查找元素为6时，由于6<9，**因为右下角的子矩阵都大于9，因此可以直接排除右下角的子矩阵**，只需要查询其他3个子矩阵即可。当然，如果中间元素等于查询的目标元素，则直接返回即可，否则在剩下的3个子矩阵中查询。

![format_png 4][]

该算法代码如下,注意边界条件，代码中加粗的部分不可省略，否则会导致代码不可终止。l==r&&u==d表示矩阵中只有一个元素，此时若不等于目标元素target，则必须返回false。

bool quadPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {  
      if (l > r || u > d) return false;  
      if (target < mat[u][l] || target > mat[d][r]) return false;  
      int col = l + (r-l)/2;  
      int row = u + (d-u)/2;  
      if (mat[row][col] == target) {  
        targetRow = row;  
        targetCol = col;  
        return true;  
      } else if (l == r && u == d) {  
        return false;  
      }  
      if (mat[row][col] > target) {  
        return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||  
               quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||  
               quadPart(mat, M, N, target, l, u, col, row, targetRow, targetCol);  
      } else {  
        return quadPart(mat, M, N, target, col+1, u, r, row, targetRow, targetCol) ||  
               quadPart(mat, M, N, target, l, row+1, col, d, targetRow, targetCol) ||  
               quadPart(mat, M, N, target, col+1, row+1, r, d, targetRow, targetCol);  
      }  
    }  
       
    bool quadPart(int mat[][N_MAX], int N, int target, int &row, int &col) {  
      return quadPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);  
    }

该算法复杂度是多少呢？可以通过公式计算：

>     原文公式： 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*      = 3*k* T(*n*/2*k*) + *c *(3k - 1)/2   = 3*k *( T(n/2*k*) + *c* ) - c/2 Setting *k* = lg *n*,  T(*n*)  = 3lg *n* ( T(1) + *c* ) - c/2       = *O*(3lg *n*)       = *O*(*n*lg 3)          <== 3lg *n = n*lg 3       = O(*n*1.58)

注：我以为这里公式应该是T(n) = 3 * T(n/4) + c ，不对的话请大家指正。

**二分算法**：

这个算法我们从矩阵中间行或者中间列或者对角线开始查找，找到s满足

>      ai < s < ai+1 ,  其中ai为矩阵中的值。

![format_png 5][]

a）从中间行查找，如查找10位于9到16之间。

![format_png 6][]

b）从中间列查找，如查找10位于9到14之间。

![format_png 7][]

c）从对角线查找，查找10位于9到17之间。

显然不管从哪里查找，都可以将原矩阵分成2个子矩阵，这样就分成了2个子问题，比起四分分解法的3个子问题，这个方法应该更好。

**代码如下，注意这里代码确定范围用的是线性查找，实际可以通过二分查找加速整个过程。**

bool binPart(int mat[][N_MAX], int M, int N, int target, int l, int u, int r, int d, int &targetRow, int &targetCol) {  
      if (l > r || u > d) return false;  
      if (target < mat[u][l] || target > mat[d][r]) return false;  
      int mid = l + (r-l)/2;  
      int row = u;  
      while (row <= d && mat[row][mid] <= target) {  
        if (mat[row][mid] == target) {  
          targetRow = row;  
          targetCol = mid;  
          return true;  
        }  
        row++;  
      }  
      return binPart(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol) ||  
             binPart(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol);  
    }  
       
    bool binPart(int mat[][N_MAX], int N, int target, int &row, int &col) {  
      return binPart(mat, N, N, target, 0, 0, N-1, N-1, row, col);  
    }

该方法复杂度的分析：为了方便，假定最后查找的子矩阵为分成了2个相同大小的子矩阵,且都为原来1/4大小。

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

如果采用二分查找确定范围，则T(n)=2T(n/4)+clgn

英文原文地址：[http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html][http_www.leetcode.com_2010_10_searching-2d-sorted-matrix-part-ii.html]

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/17014143][https_blog.csdn.net_SunnyYoona_article_details_17014143]

[20131128230328468]: https://img-blog.csdn.net/20131128230328468
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTMvMTM0MjE4ODUzNl80NzgzLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTMvMTM0MjE4ODU2NV8zODYyLnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTMvMTM0MjE4ODU3N183OTMyLmpwZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTMvMTM0MjE4ODYwNF85NjA0LmpwZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTQvMTM0MjIzMTY3Nl85OTkyLnBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTQvMTM0MjI1NjkwNV8xNTc5LnBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTQvMTM0MjI1NjkyNF85MDE5LnBuZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEyMDcvMTQvMTM0MjI1NjkzNF8xMDExLnBuZw?x-oss-process=image/format,png
[http_www.leetcode.com_2010_10_searching-2d-sorted-matrix-part-ii.html]: http://www.leetcode.com/2010/10/searching-2d-sorted-matrix-part-ii.html
[https_blog.csdn.net_SunnyYoona_article_details_17014143]: https://blog.csdn.net/SunnyYoona/article/details/17014143