首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

362个回答

添加回答
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int rowCount = array.size();
        int colCount = array[0].size();
        int i,j;
        for(i=rowCount-1,j=0;i>=0&&j<colCount;)
        {
            if(target == array[i][j])
                return true;
            if(target < array[i][j])
            {
                i--;
                continue;
            }
            if(target > array[i][j])
            {
                j++;
                continue;
            }
        }
        return false;
    }
};

编辑于 2015-06-18 16:50:07 回复(186)
从矩阵右上角进行比较,target如果等于该值,返回该值,如果比该值大,下标就往下移row+1,如果比该值小,下标就往左移cols-1。
发表于 2019-05-22 12:41:24 回复(0)
/*   先判断该值是否在数组范围内(比array[0][0]小或者比array[length-1][length-1]大,都不符合),
如果不符合,返回false;
如果符合,判断每一个一维数组最后一个是否大于target;
大于target则在该一维数组上进行二分查找,
不大于target则继续检查下一行
*/
    public boolean Find(int target, int [][] array) {
        int i = 0;
        int mid = 0;
        int hang = array.length;
        int lie = array[0].length;
        int left = 0;
        int right = lie - 1;
        //判断是否为空、大于最大值,小于最小值
        if (array[0].length==0 || array[0][0] >target || array[hang-1][right] < target) return false;
        
           //依次对每一行进行检查
        for (int j=0; j<=hang-1; j++) {
            left = 0;
            right = lie - 1;
            
            if (target > array[j][right]) {
                continue;
            }
            i = j;
                  //对每一个一维数组进行检查
            while (left < right) {
                mid = (left + right) / 2;
                if (array[i][mid] == target) return true;
                if (array[i][mid] > target) right = mid -1;
                else left = mid +1;
            }
            if (array[i][left] == target) return true;
        }
        return false;
    }

编辑于 2019-05-13 00:15:41 回复(0)

1.因为做过类似的题,第一反应就是找到一个临界点。左下角或者右上角,当数大于或者小于的时候只能向一个方向移动。没有什么好讲的,要是自己能独立思考出来很棒耶。

时间复杂度O(N)

public boolean Find(int target, int[][] array) {
        int row = array.length;//行
        int column = array[0].length;//列
        int i = row - 1, j = 0;//i 行指针 j 列指针
        while (i >= 0 && j < column) {
            if (array[i][j] == target)
                return true;
            else if (array[i][j] < target)
                j++;
            else
                i--;
        }
        return false;
    }

2.看到网上说可以通过二分法来做
思考下是怎么回事。二分法就是利用对中间数进行对比
思路是对数组的每一行进行二分查找(每行都是有序的)找到就终止循环。
没找到就先下一行。
public boolean Find(int target, int[][] array) {
    int row = array.length;//行
    for (int i = 0; i < row; i++) {
        if (dichotomy(target, array[i]))
            return true;
    }
    return false;
}
//二分法
private boolean dichotomy(int target, int[] num) {
    int left = 0, right = num.length - 1;
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (num[mid] == target)
            return true;
        else if (num[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return false;
}
时间复杂度O(NlogN)时间复杂度还稍微高一点,感觉因为少了用了一个条件:向下是递增的条件没有使用。
编辑于 2019-05-07 16:11:44 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[i].length;j++){
                if(array[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
}
发表于 2019-05-05 20:14:08 回复(0)
//先排除一些特殊情况。利用了for循环。
public class Solution {
    public boolean Find(int target, int [][] array) {

                    int i1=array.length-1;
        int i2=0;
        if(i1>=0&&i2<array[0].length) {
            
            if(target<array[0][0]) {
                return false;
            }else {
                
                
                
                for(;i1>=0;i1--) {            
                    for(i2=0;i2<array[i1].length;i2++) {
                        if(target==array[i1][i2]) {
                            return true;
                        }else if(target<array[i1][i2]){
                            break;
                        }
                    }
                }
            }
        }

            return false;


        
        
        
    }
}

编辑于 2019-05-05 17:16:25 回复(0)

求教:指出一下代码的错误。

public static boolean Find(int target, int[][] array) {
        if(array==null||array.length==0||array[0].length==0) {
            return false;
        }
        int m=array.length;
        int n=array[0].length;
        if(target<array[0][0]||target>array[m-1][n-1]) {
            return false;
        }
        find(array, target, 0);    
        return false;
    }
    //使用二分查找
    public static boolean find(int array[][],int target,int i) {
        int left=0;
        int right=array[0].length-1;
        if(i<array.length) {
            while(left<=right) {
                int mid=(left+right)/2;
                if(target==array[i][mid]) {
                    return true;
                }else if(target>array[i][mid]) {
                    left=mid+1;
                }else {
                    right=mid-1;
                }    
            }
        find(array, target, i+1);    
        }
        return false;
    }
发表于 2019-04-29 09:50:15 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int rnum = array.length;
        int hnum = array[0].length;
        int i = rnum - 1;
        int j = 0;
        boolean answer = false;
        while(i > -1 && j < hnum){
            if(target == array[i][j]){
                answer = true;
                break;
            }
            else if(target < array[i][j]){
                i--;
            }
            else {
                j++;
            }
        }
        return answer;
    }
}

发表于 2019-04-26 14:55:24 回复(0)
 public boolean Find(int target, int [][] array) {
        if ( array == null ) return false;
        for(int x = 0,y = array[0].length - 1; x < array.length && y >= 0 ; ){
            if( target == array[x][y]) return true;
            if( target > array[x][y] )
                x++;            //往下走
            else if( target < array[x][y] )
                y--;            //往左走
        }
        return false;
    }

编辑于 2019-04-24 09:14:20 回复(0)
/*
首先判断二维数组是否存在,以及target是否在二维数组中,从右上角开始比较,

如果array[ i][ j] > target 则向左走 即 j--

       如果array[ i][ j] < target 则向下走 即 i++

*/
public class Solution {
    public boolean Find(int target, int[][] array) {
        int row = (int)array.length;
        int col = (int)array[0].length;
        if(row == 0 || col == 0) {
            return false;
        }
        if(target < array[0][0] || target > array[row-1][col-1]) {
            return false;
        }
        int i=0, j=col-1;
        while(i<row && j>=0) {
            if(target < array[i][j]) {
                j--;
            }
            else if(target > array[i][j]) {
                i++;
            }
            else {
                return true;
            }
        }
        return false;
    }
}

发表于 2019-04-21 15:27:34 回复(0)
 public boolean Find(int target, int [][] array) {
        int row = array.length;
        int col = array[0].length;

        if (row<=0||col<=0)
            return false;
        if (target<array[0][0]||target>array[row-1][col-1])
            return false;

        //右上角元素坐标
        int i = 0;
        int j = col-1;

        while(i<row&&j>=0){
            int mid = array[i][j];
            if (target>mid){
                i++;
                
            }if (target<mid){
                j--;
            }if (target==mid)
                return true;
        }
       return false;
    }
1)确定右上角(左下角原理相同)一个点,矩阵上每一个数都只有两条路可以走,左或者下。
2)如果中途遇到两者相等就返回true,如果到循环结束还没遇到,即是false。
3)循环条件就是移动过程中,右上角元素行坐标不能大于总行数,列坐标不能小于0。
发表于 2019-04-19 12:19:54 回复(0)

/**不使用查找算法,直接遍历数组的每一个元素和target比较

*array.length表示二维数组的行数,array[i].length表示二维数组的列数

*/
public class Solution {
    public boolean Find(int target, int [][] array) {
         for(int i=0;i<array.length;i++){
              for(int j=0;j<array[i].length;j++){
                  if(target==array[i][j])
                      return true;
              }
         }
        return false;
    }
}

编辑于 2019-04-19 10:19:01 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array ==null || array.length<1 || array[0].length<1) return false;
        int row = array.length;
        int col = array[0].length;
        // 从右上角开始寻找(左下角开始也可以)
        for(int i=0;i<row;i++){
            for(int j=col-1;j>=0;j--){
                if(array[i][j] == target) return true;
                else if(array[i][j] < target) break; // 下一行
            }
        }
        return false;
    }
}
发表于 2019-04-18 18:15:40 回复(0)
    public boolean Find(int target, int [][] array) {
      int xLength = array.length;
      int yLength = array[0].length;
      // 依题意, 应该从 x = 0, y = yLength - 1 开始查找, 
      // array[0][0]到 a[0][yLength - 1] 和 a[0][yLength - 1] 到a[xLength - 1]y[yLength - 1]为单调递增
      // 所以当要寻找的 
      // target > array[x][y] 时, x++(因为y轴都比target小), 
      // target < array[x][y] 时, y--(因为x轴上的值都比target大),
      // 若 target == array[x][y]则找到了值, 
      // 遍历到x > xLength或y<0都没找到则数组中不包含该证书
      int x = 0;
      int y = yLength - 1;
      while (x < xLength && y >= 0) {
        if (target == array[x][y]) {
          return true;
        } else if (target > array[x][y]) {
          x++;
        } else {
          y--;
        }
      }
      return false;
    }
发表于 2019-04-17 14:55:58 回复(0)
public class Solution {
public boolean Find(int target, int [][] array) {
int i=0;
int j=array[0].length-1;
while(i<array.length&&j>=0){
if(target<array[i][j]){
j--;
}else if(target>array[i][j]){
i++;
}else{
return true;
}
}
return false;
}
}
编辑于 2019-04-16 21:37:09 回复(0)
public boolean Find(int target, int [][] array){
        for(int i=0;i<=array.length-1;i++){
               
                if(Arrays.binarySearch(array[i],target)>=0){
                    return true;}

        }
      
        return false;
    }


发表于 2019-04-15 21:27:20 回复(0)
我们从右上角开始遍历,对于当前所选的数(左边与之同行的数都比它小,下面与之同列的数都比它大),如果等于目标则返回TRUE;如果大于目标值,则j--;如果小于目标值,则i++;如果遍历完整个数组没有找到则返回FALSE;
public class Solution {
    public boolean Find(int target, int [][] array) {
        int m=array.length,n=array[0].length;
        if(array==null||m==0||n==0) return false;
        int i=0,j=n-1;
        while(i<m&&j>=0){
            if(array[i][j]==target) return true;
            else if(array[i][j]>target)j--;
            else i++;
                
             
        }
        return false;
    }
}

发表于 2019-04-13 14:29:10 回复(0)
思路:数与数的比较一共三种可能性:小于,等于,大于。使用两次for循环,逐一比较,遇到等于返回true,又由于数组以递增排序,所以遇到比target大的数,可以使用break跳出循环。
public class Solution {
    public boolean Find(int target, int [][] array) {
        
        int N = array[0].length;
       //行逐一比较,
        int C = array.length;
        for(int i = 0;i<C ;i++){
            for(int j = 0;j<N;j++){
               // if(target>array[i][j]) j++;
                if(target == array[i][j]) return true;
                if(target < array[i][j]) break;
            }
        }
        return false;
    }
}

发表于 2019-04-12 16:08:09 回复(0)