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

300个回答

添加回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(158)
自己想了一种二分法结合递归求解的方法,貌似时间复杂度为lg2n,想和大家讨论一下
import java.util.Arrays;
public class Solution {
     public boolean Find(int target, int [][] array) {
        int rowNum = array==null?0:array.length;
        int colNum = array==null?0:array[0].length;
        if(rowNum==0 || colNum==0) return false;
        return search(target, array, 0, rowNum-1, 0, colNum);
    }
    
    public boolean search(int target, int[][] array, int rowstart, int rowend, int colstart, int colend){
        if(rowstart>rowend || colstart>=colend){
            return false;
        }
        int rowSearch = (rowstart+rowend)/2;
        int result = Arrays.binarySearch(array[rowSearch], colstart, colend, target);
        if(result>=0){
            return true;
        }else{
            int insertionPoint = -result-1;
            return search(target, array, rowstart, rowSearch-1, insertionPoint, colend) 
                   ||  search(target, array, rowSearch+1, rowend, colstart, insertionPoint);
        }
    }

}
发表于 今天 12:56:57 回复(0)
/*
4种思路:
1.暴力解决法:不考虑行列递增特性
2.二分查找法:考虑行递增特性
3.改良二分查找法:考虑行列递增特性
4.矩阵寻路法:考虑行列递增特性
*/
//改良二分查找法:
public class Solution {
public boolean Find(int target, int [][] array) {
    int high=array.length-1;
    int low=0;
    int mid;
    for(int i=0;i<array[0].length;i++){
        while(low<=high){
            mid=(low+high)/2;
            if(array[i][mid]>target)
                high=mid-1;
            else if(array[i][mid]<target)
                low=mid+1;
            else
                return true;
        }
        if(low==0&&high==-1)
            return false;
        low=0;
    }
        return false;
    }
}
//矩阵左下角寻路法
public class Solution {
public boolean Find(int target, int [][] array) {
    int j=array[0].length-1;
    int i=0;
    while(i<=array.length-1&&j>=0){
        if(array[i][j]>target)
            j--;
        else if(array[i][j]<target)
            i++;
        else
            return true;
    }
    return false;
  }
}

编辑于 2019-01-08 11:53:11 回复(0)
解题思路:
由题可知对于当前题的二维数组的特性(从上到下依次递增,从左到右依次递增)可以得知当将target与当前二维数组中的任一元素进行比较时,都可以推出得一个结论是:
target > array[row][col], 即target大于当前的元素时,那么target 只有可能出现在当前元素所在列的下边,则有 row ++.
target < array[row][col], 即target小于当前的元素时,那么target 只有可能出现在当前元素所在行的右边, 则有 col--.
时间复杂度为:M+N (M为行数,N为列数)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int col = array[0].length - 1;
        int row = 0;
        while(row <= array.length - 1 && col >= 0){
            if(target == array[row][col])
                return true;
            else if (target > array[row][col])
                row++;
            else
                col--;
        }
        return false;
    }
}
发表于 2019-01-05 19:01:07 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        return  Arrays.stream(array).flatMapToInt(Arrays::stream).anyMatch(num -> num == target);
    }
}


为什么这段代码他说不正确
发表于 2018-12-27 16:05:10 回复(0)
思路:
1.根据题意我们知道,每一行的最后一个元素是当前这一行最大的,当前这一列最小的
2.所以分为三种情况:
    a)当右上角这一个元素值比查找的数小时:当前这一行最大元素就是右上角所处的元素,所以就应该在下面的行里面查找,即row++
    b)当右上角这一个元素值比查找的数大时:当前这一列最小元素就是右上角所处的元素,所以就应该在左边的列里面查找,即col--
    c)当右上角这一个元素值等于查找的数时,那么就查找到了元素
代码:
public class Solution {
    
    public boolean Find(int target ,int [][]array){
        boolean flag = false;
        
        int rows = array.length;
        
        if(rows > 0){
            int cols = array[0].length;
            int row = 0;
            int col = cols - 1;
            while(row < rows && col >= 0){
                if(array[row][col] == target){
                    flag = true;
                    break;
                }
                if(array[row][col] > target){
                    col--;
                }else if(array[row][col] < target){
                    row++;
                }
            }
        }
        
        return flag;
    }

}


发表于 2018-12-25 20:57:10 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        boolean tag = false;
        for(int i = 0 ; i < array.length ; i++){
            for(int j = 0 ; j < array[0].length ; j++) {
                if(array[i][j] == target){
                    tag = true;
                }
            }
        }
        return tag;
    }
}

发表于 2018-12-24 11:27:11 回复(0)
先进行边界处理
从二维数组右上角开始
如若比target大,排除这一行。往下走。
如若比target小,排除这一列,往左走。
利用数组的有序性
发表于 2018-12-21 13:19:01 回复(0)
矩阵是从左到右从上到下有序的,所以选择从矩阵的一个角开始比较容易,比如左下角开始,如何左下角数大于目标值,则行数减一这样排除了最后一行往上一行走再比较,如何此时小于目标值则列数加一这样排除了第一列往右走再继续比较......以此类推,在行数大于0列数小于最大列数之内,不满足大于和小于就是等于,即找到目标值,如果行数列数其中一个不满足则循环结束,返回false,
以下是我的JAVA代码:
public class Solution {
    public boolean Find(int target, int [][] array) {
        int n=array.length-1;  
        int m=array[0].length;
        int i=0;
        while(n>=0&&i<m){
            if(array[n][i]>target){
            n--;}
        else if(array[n][i]<target){
            i++;}
            else{
                 return true;
        }
       
        }
        return false;
        
    }
}




发表于 2018-12-14 14:58:40 回复(0)
从左下角开始进行比较:
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;
    }
}

编辑于 2018-12-13 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)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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