java在排序矩阵中查找元素

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的链接 Find the first element in a sorted array that is greater than the target

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

boolean FindElem(int[][] mat, int elem, int M, int N) {
 int row = 0;
 int col = N-1;
 while (row < M && col >= 0) {
   if (mat[row][col] == elem) {
     return true;
   } else if (mat[row][col] > elem) {
     col--;
   } else {
     row++;
   }
 }
   return false;
}

Answer 2

以下是我要尝试的。给定一个mby n矩阵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的特例。我在谷歌上搜索了一个年轻的画面，找到了this article which gives 3 nice approaches（第一个（也是最差的一个），就是我上面描述的那个）

Answer 3

你的算法可能是O（logm+logn），但它也给出了错误的答案

假设您在以下矩阵中搜索“4”（其中左上角为row=0，col=0）：

0 1 4
1 2 5
2 3 6

你的算法从中间的2开始。因为4大于2，所以继续搜索同一行（不在那里）、同一列（不在那里）和右下角（不在那里）。哎呀

对每一行和每一列进行排序的约束实际上相当弱。特别是，对角线上的元素可以是任何顺序

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

不知道该如何分析这个的性能

Answer 4

对于基于比较的算法，O（lg（m）+lg（n））查询是最优的

证明

对于基于比较的查询，每个查询只能有两个结果：true或false。一个明显的扩展是，对于N个查询，最多可以有2个^N结果。因此，使用N个查询，您只能在最多包含2个^N元素的矩阵中定位元素

搜索一个m x n矩阵需要多少查询？为N解决问题

2^N=mn
lg（2^N）=lg（mn）
N=lg（m）+lg（N）

因此lg（m）+lg（n）查询是最优的

基于非比较的查询

这个证据是决定性的，但只适用于基于比较的查询。如果你以一种不涉及比较的方式查询矩阵，那么如果你知道值的分布，你可以得到接近常数的时间。我不会给你一个算法，但我建议你看看Radix sort，因为它包含一种基于非比较的技术，这是打破lg（m）+lg（n）下限所必需的

Answer 5

从矩阵的左下角开始。然后向右走，直到你找到确切的数字（完成），或者直到你找到一个更大的数字

然后在矩阵中向上移动，直到找到确切的数字（完成），或者直到找到一个太小的数字

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

以下图像包含一些示例，使用Excel表格以绿色显示目标编号，以黄色显示路径

在最后一个例子中，我们寻找207，它不在矩阵中：

这就是算法。编码留给您作为练习：-）

编辑：从最下面一行开始时，二进制搜索可能会提供更好的起点。对于算法的其余部分，这可能无关紧要

Answer 6

阅读之前的评论，我想出了这个算法。它基本上假设从右上角开始，矩阵可以用作带有一些“循环”的BST（我们不关心这个循环）

1 4 9
5 6 10

     9
    /  \
   4   10
  / \  /
 1   6
  \ /
   5

该算法与在BST中搜索相同，非常容易理解。最坏情况下的运行时间是O（n+m）

public static boolean search( int[][] matrix, int value )
{   
    int rows = matrix.length;
    int columns = matrix[0].length;

    int i = 0;
    int j = columns - 1;

    while( i < rows
           && j >= 0 )
    {   
        if( matrix[i][j] == value )
        {
            System.out.println( "Found at " + i + " " + j );
            return true;
        }

        if( matrix[i][j] < value )
        {
            j--;
        }
        else
        {
            i++;
        }
    }

    return false;
}