在排序矩阵中查找元素

Question

问题:给定一个矩阵,其中每行和每列都被排序,编写一个方法来查找其中的元素.

这是一个经典的面试问题,这是我的解决方案

boolean F(int[][] matrix, int hs, int he, int ws, int we)
{
    if (hs > he || ws > we) 
        return false; 

    int m = (hs + he) / 2; 
    int n = (ws + we) / 2;

    if (matrix[m][n] == t)
    {
        return true;
    }
    else if (matrix[m][n] < t)
    {
        // find the ele in the same row, right to [m][n]
        F(m, m, n + 1, we);

        // find the ele in the same col, upper to [m][n]
        F(m + 1, he, n, n);

        // find the ele in the area, where i>m,j>n 
        F(m + 1, he, n + 1, we);       
    } 
    else if (matrix[m][n] > t)
    {
        // very similar to previous part
    }
}

算法的运行时间是log(m)+ log(n).我正在寻找一种更高效的算法,或者使用简洁的代码.

有了更多评论,我想出了以下代码:

// return target recurrence in the matrix
int F(int[][] m, int rs, int re, int cs, int ce, int t){
   int r1 = rs, r2 = re;
   int c1 = cs, c2 = ce;
   int r=0 , c = c1;

   while( r1 < r2 && c1 < c2 ){
   // find the last element that <= t in column c
     r  = FlastLess( r1, r2, c, t)

     if( r == -1 ) break;

     else{
       // find the first ele in the row that is >=t
       c = FfirstGreater( r, c1, c2, t);

       if( c == -1)  break;
       else{
         r2 = r; 
         c1 = c; 
       }// else    
     }// else 
   }// while
}// f

以下是函数F1和F2的链接 查找排序数组中大于目标的第一个元素

void FlastLess(int s, int e, int t){
  int l = s, h = e;
  while( l != h ){
     int mid = (l+h)/2;
     if( mid >=  t) high = mid - 1; 
     else {
       if( high < t) low= mid + 1;
       else low = mid;
     } 
  }

 void FfirstGreater(int s, int e, int t){
  while(l < h){
    mid = (l+h)/2;
    if ( mid <=  t) low = mid+1;
    else high = mid;
  }
 }

}

Answer 1

从矩阵的左下角开始.然后向右走,直到找到确切的数字(完成),或直到找到更大的数字.

然后你在矩阵中向上,直到找到确切的数字(完成),或直到找到一个太小的数字.

然后再向右移动,......依此类推,直到找到数字或直到你到达矩阵的右侧或顶部.

以下图像包含一些示例,使用Excel表格显示绿色的目标编号,以及黄色跟随的路径.

在最后一个例子中,我们查找207,它不在矩阵中:

这只是算法.编码留给你作为练习:-)

编辑:当从底行开始时,二进制搜索可能会提供更好的起点.对于算法的其余部分,它可能无关紧要.

Answer 2

您的算法可能是O(log m + log n),但它也给出了错误的答案.

假设您在以下矩阵中搜索"4"(其中左上角是row = 0,col = 0):

0 1 4
1 2 5
2 3 6

您的算法首先查看2中心.由于4大于2,您继续搜索同一行(不存在),同一列(不存在)和右下角(不存在).哎呦.

每个行和列的排序约束实际上非常弱.特别地,沿对角线的元素可以是任何顺序.

我认为正确的方法是在第一列和最后一列进行二进制搜索,以缩小可能行的范围.然后对这些行的第一行和最后一行进行二进制搜索,以缩小可能的列.等等.

不知道如何分析这一个的表现......

Answer 3

这就是我要尝试的。给定一个mbyn矩阵A，将值X与条目进行比较A(m/2,n/2)（如有必要，请使用楼层）。

如果A(m/2,n/2) == X，完成。

如果A(m/2,n/2) < X，则需要检查 3 个较小的矩阵：

A(1:m/2, 1:n/2) 
A(1:m/2, n/2+1:n) 
A(m/2+1:m, 1:n/2) 

如果A(m/2,n/2) > X, ，则需要检查 3 个较小的矩阵：

A(m/2:m, n/2:n) 
A(1:m/2, n/2+1:n) 
A(m/2+1:m, 1:n/2) 

您可以通过将值与相应矩阵中的最小值（左上值）进行比较来消除其中两个（并非总是如此）。然后，您递归地尝试查找每个剩余矩阵中的值。

其复杂度约为O((n*m)^0.8).

行和列排序的矩阵是Young tableau的特例。我在 google 上搜索了 Young tableau，发现这篇文章提供了 3 种不错的方法（第一个（也是最差的）就是我上面描述的那个）。