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

291个回答

添加回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(157)
从左下角开始进行比较:
public class Solution {
public boolean Find(int target, int [][] array) {
int rows = array.length;
int clos = array[0].length;
int i = rows - 1,j = 0;
while(i >= 0 && j < clos){
if(target > array[i][j])
j++;
else if(target < array[i][j])
i--;
else
return true;
}
return false;
}
}

从右上角进行比较:
public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int i = 0,j = cols - 1;
        while(i<rows && j>=0){
            if(target>array[i][j])
                i++;
            else if(target<array[i][j])
                j--;
            else
                return true;
        }
        return false;
    }
}

编辑于 今天 09:25:10 回复(0)
  • 首先,解题的思路其实利用了二维数组的从小到大的性质,从二维数组矩阵的右上或者左下开始比较都是可以的。

  • 其次,我们要注意向量的溢出等问题,比如:如果二维向量为空怎么办?我认为这些思考是编程素养的体现。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int raws = array.length; //行
        int cols = array[0].length; //列
        int i = 0;
        int j = cols -1;
        //printf("%d,%d",raws,cols);
        //int totalnums = raws * cols; //元素总个
        if(raws == 0 || cols == 0)
            return false;
        if(target >= array[0][0] && target <= array[raws-1][cols-1]){
            while(i=0){
                if(target == array[i][j])
                    return true;
                else if(target < array[i][j])
                    j--;
                else
                    i++;
            }
        }
        return false;
    }
}
发表于 2018-12-11 02:10:02 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int i = 0,j = array[0].length-1;
        while(i < array.length && j >= 0) {
            if(target < array[i][j]) {
                /* 删除该列 */
                j--;
            } else if(target == array[i][j]) {
                return true;
            } else {
                /* 删除该行 */
                i++;
            }
        }
        return false;
    }
} 
选取数组右上角的数字。如果target小于这个数字,那么根据题意,这一列下面的所有数字都比他大,因此这列可以删掉。如果target大于这个数字,那么target可能在这一列下面出现,也可能在这个数字的左下方出现,但绝对不会在本行出现,因此该行可以删掉。
发表于 2018-12-10 22:39:15 回复(0)
个人建议用我的解题思路:
    列如一个二维数组 int arr[][] = {{1,2,9},{3,4,10},{5,7,12}}
    我们查找二维数组里面是否存在 7
    我们可以先从最右边算起 拿9和7作比较,显然9后面的一列都不符合,在计算倒数第二列2小于7,那么选择在第倒数第二列中查看是否有7,参考代码如下
    public class Test{
            public static boolean(int[][] arr, int find){
                    int rows = arr.length;//一共有多少行
                    int cols = arr[0].length//第一行的个数
                    int i = 0; //第一行第一个数的下标
                    int j = cols - 1;//第一行最后一个下标
                    while(i<rows&&j>=0){
                        if(arr[i][j]>find){
                            j--;
                            continue;
                        }
                        else if(arr[i][j]<find){
                            i++;
                            continue;
                        }
                        else{
                            renturn true;
                        }
        }
                        return false;
    }
}
    
发表于 2018-12-06 21:38:22 回复(0)
/**
     * 从左下角开始搜索
     * 若小于该数字,列数右移
     * 若大于该数字,行数上移
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int[][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int row = rows - 1;
        int col = 0;
        while (col <= cols - 1 && row >= 0) {
            if (target == array[row][col])
                return true;
            else if (array[row][col] < target)
                col++; //遍历的数字小于该target数,则找寻更大数,列数右移
            else
                row--;//遍历的数字大于该target数,则找寻更小数,行数上移
        }
        return false;
    }

发表于 2018-12-04 15:50:40 回复(0)
没有想象的那么复杂,只是一个简单的二维数组的遍历问题,至于楼上说的很多特殊情况,其实都是可以简化的,很多的特殊情况就相当没有执行for,返回的就是false
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;
    }
}
发表于 2018-12-02 18:36:38 回复(0)
public class solution_1 {

    public boolean Find(int [][] array, int target){
        int m = array.length - 1;    //左下角的行
        int i = 0;    //左下角的列


        if (array == null || array[0].length == 0) {    //当数组为空,或者是一维数组的时候返回false
            return false;
        }
        while(m >= 0 && i <= array[0].length - 1){  //设置搜索范围保证第一行的第一个和最后一行的最后一个都可以被搜索到
            if (array[m][i] > target){
                m --;
            }
            else if (array[m][i] < target){
                i ++;
            }
            else
                return true;


        }
        return false;
    }
}
发表于 2018-11-30 18:54:24 回复(0)
    public boolean Find(int target, int [][] array) {
        int row = 0;
        int col = array[0].length-1;
       while(row<array.length&& col>=0){
            if(array[row][col] == target){
                return true;
            }
           else if(array[row][col] > target){
               col--;
           }
           else{
               row++;
           }
       }
        return false;
    } 
思路如下,我们需要找到这样一个元素,从右上角开始,若小,删除一行,若大,向左走, 删除一列 
利用二维数组由上到下,由左到右递增的规律 , 选取右上角的元素array[row][col]target进行比较 
target小于array[row][col],那么target必定在左边,这时候可以col-- 
traget大于array[row][col],那么target必定在下边,这时候可以row++ 

发表于 2018-11-28 15:51:51 回复(0)
从最左下角的元素开始判断,这个位置的值有个特点,其右边的值比它大,上面的数比它小,将进来的那个数与左下角的那个数进行比较,大之则焦点右移动,小之则焦点上移,如果焦点都移除边界了还没有找到相同的数,则这个二维数组没有这个数.

public class Solution {
    public boolean Find(int target, int [][] array) {
       //得到二维数组的高宽
        int m = array.length;
        int n = array[0].length;
        /设置初始坐标为左下角的坐标
        int x = m-1;
        int y = 0;
        while(x >= 0 && y < n){
        int z = array[x][y];
        if(target > z){
            y = y+1;
        }else if(target < z){
            x = x-1;
        }else{
           return true;
        }
       }
        return false;
    }
}
发表于 2018-11-27 22:09:04 回复(0)
    public boolean Find(int target, int [][] array) {
        int i=array.length-1;      //最大行数
        int j=0;    //第一个i,j初始值为左下角的数
        
        while(i>=0&&j<array[0].length){   //边界判断
            if(array[i][j]== target )
                return true;
            
            else if (array[i][j] < target){     //大于则右移
                j++;
            }
            
            else{                  //小于则上移
                i--;
            }
        }
        return false;
    }

受教后改进的算法,收益匪浅。
发表于 2018-11-26 16:27:10 回复(0)
 解题思路:
     二维数组是有序的,从左下角来看,向右数字递增,向上数字递减
     当查找的数字比左下角数字小时,上移
     当查找的数字比左下角数字大时,右移
     或
     二维数组是有序的,从右上角来看,向左数字递减,向下数字递增
     当查找的数字比右上角数字小时,左移
     当查找的数字比右上角数字大时,下移

以下解题方式是从左下角来解题:
public class Solution {
    public boolean Find(int num, int [][] array) {
          if (array == null || array.length == 0 || array[0].length == 0)
        {
            return false;
        }
        //一维数组下标
        int n = array.length - 1;
        //二维数组下标
        int m = 0;
        int temp = array[n][m];
        while (num != temp)
        {
            if (n > 0 && m < array[0].length)
            {
                if (num > temp && m < array[0].length - 1)
                {
                    m++;
                } else
                {
                    n--;
                }
                temp = array[n][m];
            } else
            {
                return false;
            }
        }
        System.out.println("n="+n+","+"m:"+m);
        return true;
    }
}

发表于 2018-11-21 16:06:14 回复(0)

请问为什么我的代码在本机上能运行成功,在牛客上运行不了呢?

下面是我在牛客上的代码

public class Solution {
    int[][] myarr;
    int myTar = 0;
    public boolean Find(int target, int [][] array) {
        myarr = array;
        myTar = target;
        return myFind(0,0,array[0].length-1, array.length-1);
    }
    public boolean myFind(int x1, int y1, int x2, int y2){

        int i = 0;
        for(i = 0;i <= x2 - x1&&i <= y2 - y1;i++){
            if(myarr[i + y1][i + x1] == myTar)
                return true;
            else if(myarr[i + y1][i + x1] > myTar){
                if(i == 0)return false;
                return myFind(x1, y1+i, x1+i-1, y2)||myFind(x1+i, y1, x2, y1+i-1);
            }
        }
        if(x2-x1 == y2-y1)return false;
        else if(x2 - x1 > y2-y1)
            return myFind(x1+y2-y1+1,y1,x2,y2);
        else if(x2 - x1 < y2 - y1)
            return myFind(x1,y1+x2-x1+1,x2,y2);
        return false;
    }
}

这是我在本机上的代码,就只把solution类的public去掉了而已:

public class Main {
    public static void main(String[] args){
        int[][] a = new int[30][50];
        for (int i = 0; i < 30; i++) {
            for (int j = 0; j < 50; j++) {
                a[i][j] = i*10+j;
            }
        }
        Solution s = new Solution();
        System.out.println(s.Find(100000,a));
    }
}

class Solution {
    int[][] myarr;
    int myTar = 0;
    public boolean Find(int target, int [][] array) {
        myarr = array;
        myTar = target;
        return myFind(0,0,array[0].length-1, array.length-1);
    }
    public boolean myFind(int x1, int y1, int x2, int y2){

        int i = 0;
        for(i = 0;i <= x2 - x1&&i <= y2 - y1;i++){
            if(myarr[i + y1][i + x1] == myTar)
                return true;
            else if(myarr[i + y1][i + x1] > myTar){
                if(i == 0)return false;
                return myFind(x1, y1+i, x1+i-1, y2)||myFind(x1+i, y1, x2, y1+i-1);
            }
        }
        if(x2-x1 == y2-y1)return false;
        else if(x2 - x1 > y2-y1)
            return myFind(x1+y2-y1+1,y1,x2,y2);
        else if(x2 - x1 < y2 - y1)
            return myFind(x1,y1+x2-x1+1,x2,y2);
        return false;
    }
}
发表于 2018-11-19 20:44:53 回复(0)
public static boolean find(int target, int[][] array) {
        int tR = 0, tC = array[0].length - 1;
        while (tR < array.length && tC > -1) {
            if (target < array[tR][tC]) { tC--; } else if (target > array[tR][tC]) {
                tR++;
            } else {
                return true;
            }
        }
        return false;
    }

编辑于 2018-11-16 18:41:07 回复(0)
编译错误:您提交的代码无法完成编译
Main.java:25: error: incompatible types: int cannot be converted to int[][]
boolean ret = solution.Find(target, array);
为啥会有这个错误?
发表于 2018-11-09 15:33:29 回复(2)

二维数组遍历

public class Solution {
    public boolean Find(int target, int [][] array) {
    for (int[] j : array) {
        for (int i : j) {
         if (target == i)
            return true;
            }
        }
     return false;
    }
}
发表于 2018-11-08 15:38:41 回复(0)
            boolean temp=false;
        for (int a = 0; a < array.length; a++) {
            for (int c = 0; c < array[a].length; c++) {
                if (target == array[a][c]) {
                    temp= true;
                }

            }
        }
        return temp;

发表于 2018-11-07 16:28:13 回复(0)
剑指offer 03

public class Solution {
    /**
     * 每次截掉一行或一列, 复杂度m+n
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int[][] array) {
        //参数检查
        if(array == null) {
            return false;
        }

        int rows = array.length;
        int cols = array[0].length;
        
        //从右上角开始查找
        int row = 0;
        int col = cols - 1;
        while(row<rows && col>=0) {
            if(array[row][col] == target) {
                return true;
            }else if(array[row][col] > target) {
                col--;
            } else {
                row++;
            }
        }

//        //如果从左下角开始查找
//        int row = rows - 1;
//        int col = 0;
//        while(row>=0 && col<cols) {
//            if(array[row][col] == target) {
//                return true;
//            }else if(array[row][col] < target) {
//                col++;
//            } else {
//                row--;
//            }
//        }

        return false;
    }
}

发表于 2018-11-04 15:00:05 回复(0)
思路就不说了,我说一下自己做错的地方,就是我刚开始是从右下角开始做的,这个二维数组可以从左下角和右上角开始做,但是不能从左上角和右下角。我开始做的时候从右下角开始,这样是无法缩小排查范围的。所以起始点要选对
发表于 2018-11-04 09:13:10 回复(0)
  for(int i = 0; i < str.length();i++){ if(str.charAt(i) == ' ' ) {
            
              str.replace(i, i + 1, "%20");
          }
      } return str.toString();
发表于 2018-11-02 21:41:59 回复(0)
//各位大佬,我这解题方式怎么样,问题大不大
public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = array.length-1;
        int col = array[0].length;
        for (int i = 0; i < array[row].length;) {    
            if(target==array[row][i]){
                return true;
            
            i++;
            if(i>=col){
                row--; i = 0;
                if(row<0){
                    return false;
                }
                continue;
            }        
        }
        return false;
    }
}
发表于 2018-10-30 22:47:13 回复(0)

扫一扫,把题目装进口袋

牛客网,程序员必备求职神器

扫描二维码,进入QQ群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号