在已排序矩阵中查找元素 [英] find an element in a sorted matrix

问题描述

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

Problem: Given a matrix in which each row and each column is sorted, write a method to find an element in it.

这是一道经典的面试题，这是我的答案

It is a classic interview question, here is my solution

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).我正在寻找一种更高效或代码简洁的算法.

The running time of the algorithm is log(m) + log(n). I am looking for an algorithm that is more efficient, or with concise code.

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

Having more comments, I come up with following code:

// 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 的链接找到第一个元素大于目标的排序数组

Here is the link to function F1 and 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;
  }
 }

}

推荐答案

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

Start in the bottom-left corner of your matrix. Then go to the right until you find the exact number (done), or until you find a number that is bigger.

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

Then you go upwards in the matrix until you find the exact number (done), or until you find a number that is too small.

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

Then again you move to the right, ... and so on until you found the number or until you reach the right-side or top of your matrix.

以下图片包含一些示例，使用 Excel 表格，绿色显示目标数字，黄色显示路径.

The following images contain some examples, using an Excel table showing the target number in green, and the path that is followed in yellow.

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

In the last example we look for 207, which isn't in the matrix:

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

This is just the algorithm. The coding is left for you as an exercise :-)

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

When starting on the bottom row, a binary search might give a better starting point. For the rest of the algorithm it probably doesn't matter.

这篇关于在已排序矩阵中查找元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！