现在的位置: 首页 > 综合 > 正文

杨氏矩阵搜索算法

2013年09月11日 ⁄ 综合 ⁄ 共 3536字 ⁄ 字号 评论关闭

问题:已知一个2维矩阵,其中的元素每一行从左至右依次增加,每一列从上到下依次增加。即对于矩阵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步,即从右上角开始查找,而要查找的目标值在左下角的时候。

代码如下:

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个子矩阵中查询。

该算法代码如下,注意边界条件,代码中加粗的部分不可省略,否则会导致代码不可终止。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      = 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个子问题,这个方法应该更好。

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

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

 

抱歉!评论已关闭.