首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数:2367260 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]

给定 target = 7,返回 true。

给定 target = 3,返回 false。

数据范围:矩阵的长宽满足 , 矩阵中的值满足
进阶:空间复杂度 ,时间复杂度
示例1

输入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

true

说明

存在7,返回true   
示例2

输入

1,[[2]]

输出

false
示例3

输入

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

输出

false

说明

不存在3,返回false   
C++11标准有一个范围for语句,题目的数组使用vector<vector<int> >表示的二维数组,先用范围for语句取出一位数组中的内容存放到一个变量i中去(变量的类型使用C++11标准的auto来去获取),然后再用范围for语句取出上述变量i里数组的每一个内容。
如果对C++11标准的范围for语句和auto有了解,这道题是十分容易的,而且代码十分精炼。班门弄斧了,不喜勿喷。
class Solution 
{
public:
    bool Find(int target, vector<vector<int> > array) 
    {
        for (auto i: array)
        {
            for(auto j: i)
            {
                if(target == j)
                	return true;
            }
        }
        return false;
    }
};

编辑于 2017-03-29 20:47:52 回复(0)
更多回答
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

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 回复(249)
两种思路
一种是:
把每一行看成有序递增的数组,
利用二分查找,
通过遍历每一行得到答案,
时间复杂度是nlogn
public class Solution {
    public boolean Find(int [][] array,int target) {
        
        for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;

    }
}

另外一种思路是:
利用二维数组由上到下,由左到右递增的规律,
那么选取右上角或者左下角的元素a[row][col]与target进行比较,
当target小于元素a[row][col]时,那么target必定在元素a所在行的左边,
即col--;
当target大于元素a[row][col]时,那么target必定在元素a所在列的下边,
即row++;
public class Solution {
    public boolean Find(int [][] array,int target) {
        int row=0;
        int col=array[0].length-1;
        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;

    }
}

编辑于 2015-12-21 22:58:19 回复(70)

最高效最简洁的写法15行给你

分析题目:

明显是查找题。查找分两种,无规则无序查找(联想经典算法,根据复杂度和条件选择之一)和相对有序查找(本题)。相对有序查找一般要多分析排序规则。

题规则特点:

左上右下,分别是最小和最大值。左下和右上呢?分别是最后一行最小值&第一列最大值和第一行最大值&最后一列最小值。由此,我们可以想象,从左下的点为current-point,如target > cur-point 则候选区域可以排除第一列,排除后新的矩阵左下为[2,N]target > cur-point则候选区域可排除最后一行,排除后新的矩阵左下为[1,N-1]。以此类推到停止条件。

思路:

由此,我们可以想象,从左下的点为current-point,如target > cur-point 则候选区域可以排除第一列,排除后新的矩阵左下为[2,N]。如target > cur-point则候选区域可排除最后一行,排除后新的矩阵左下为[1,N-1]。以此类推到停止条件。
    def Find( self, target, array):
    # write code here
        if len(array) == 0:
            return False
        High = len(array)
        Wigth = len(array[0])
        high = High -1
        wight = 0
        while high >= 0 and wight < Wigth:
            cur = array[high][wight]
            if target == cur:
                return True
            elif target > cur:
                wight = wight + 1
            else:
                high = high - 1
        return False


编辑于 2020-06-29 02:29:52 回复(0)
从左下角元素往上查找,右边元素是比这个元素大,上边是的元素比这个元素小。于是,target比这个元素小就往上找,比这个元素大就往右找。如果出了边界,则说明二维数组中不存在target元素。

Python版本
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array) - 1
        cols= len(array[0]) - 1
        i = rows
        j = 0
        while j<=cols and i>=0:
            if target<array[i][j]:
                i -= 1
            elif target>array[i][j]:
                j += 1
            else:
                return True
        return False

C++版本
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        // array是二维数组,这里没做判空操作
        int rows = array.size();
        int cols = array[0].size();
        int i=rows-1,j=0;//左下角元素坐标
        while(i>=0 && j<cols){//使其不超出数组范围
            if(target<array[i][j])
                i--;//查找的元素较少,往上找
            else if(target>array[i][j])
                j++;//查找元素较大,往右找
            else
                return true;//找到 
        }
        return false;
    }
};

Java版本
public class Solution {
    public boolean Find(int target, int [][] array) {
        int rows = array.length;
        int cols = array[0].length;
        int i=rows-1,j=0;
        while(i>=0 && j<cols){
            if(target<array[i][j])
                i--;
            else if(target>array[i][j])
                j++;
            else
                return true;
        }
        return false;
    }
}

编辑于 2017-07-20 17:04:43 回复(34)
最佳答案:没有之一。思路:首先我们选择从左下角开始搜寻,(为什么不从左上角开始搜寻,左上角向右和向下都是递增,那么对于一个点,对于向右和向下会产生一个岔路;如果我们选择从左下脚开始搜寻的话,如果大于就向右,如果小于就向下)。
public class Solution {
    public boolean Find(int [][] array,int target) {
int len = array.length-1;
        int i = 0;
        while((len >= 0)&& (i < array[0].length)){
            if(array[len][i] > target){
                len--;
            }else if(array[len][i] < target){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }
}
发表于 2015-08-26 14:14:12 回复(67)
想了很久才想到从左下角开始遍历,思路和大家一样。自认为自己的代码比较简洁,不知道效率是是不是一样。实现的过程中也遇到几个问题,在这里贴出来分享一下。
public class Solution {
    public boolean Find(int target, int [][] array) {
		int m = array.length;
        int n = array[0].length;
        int i = m-1,j = 0;
        while(true) {
        	if(i == -1 || j == n)    //进行边界判断,原来是在两个elseif里判断的,但是空数组的话会有异常
        		return false;
        	if(target == array[i][j])
        		return true;
        	else if(target < array[i][j])    //这里用elseif,原来用的是if,移位后array[i][j]发生改变,下面的判断有可能为true造成结果错误。使用elseif也会减少比较次数
        		i--;
        	else if(target > array[i][j])
        		j++;
        }
    }
}

发表于 2017-03-05 19:34:36 回复(0)
/*
	算法思想:首先选取数组中右上角的数字,如果该数字等于要查找的数字,则查找过程结束;如果该数字大于要查找的数字,剔除这个数字所在的列;
    如果该数字小于要查找的数字,剔除这个数字所在的行。这样每一步都可以缩小查找范围,直到找到要查找的数字,或者查找范围为空为止。*/
    public class Solution {
    public boolean Find(int target, int [][] array) {
		//boolean found = false;
        int i = 0,j = array[0].length - 1;
        while(i <= array.length - 1  && j >= 0){
            if(array[i][j] == target){
                return true;
                //break;
            }else if(array[i][j] > target){
                j--;
                continue;
            }
            else{
                i++;
                continue;
            }
        }
        return false;
    }
}

发表于 2017-02-25 22:01:45 回复(2)
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        for (auto &i : array){
            int left = 0;
            int right = i.size() - 1;
            while (left <= right) {
                int mild = (left + right) / 2;
                if (i[mild] > target) {
                    right = mild - 1;
                } else if (i[mild] < target) {
                    left = mild + 1;
                } else {
                    return true;
                }
            }
        }
        return false;
    }
};

二分法查找。二维数组就是要多遍历一遍一维的内容。
发表于 2022-08-14 14:47:29 回复(0)
将二级指针看成一个一维的指针数组,存放的是指向一维数组的地址
每层使用二分查找
bool search(int* arr,int target,int arrayColLen)
{
    int left=0,right=arrayColLen-1;
    int mid=0;
      while(left<=right)
        {
            mid=left+(right-left>>1);
            if(arr[mid]>target)
            {
                right=mid-1;
            }
            else if(arr[mid]<target)
            {
                left=mid+1;
            }
            else
            {
                return true;
            }
        }
    return false;
}
bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
   while (arrayRowLen--)
    {
        if (search(*array, target, *arrayColLen))
        {
            return true;
        }
        array++;
    }
    return false;
}

发表于 2022-07-31 21:52:45 回复(0)
Java一行代码。暴力解法。
public class Solution {
    public boolean Find(int target, int [][] array) {
        return Arrays.stream(array).flatMapToInt(Arrays::stream).anyMatch(
                   i -> i == target);
    }
}
发表于 2022-07-05 22:40:23 回复(0)
public class Solution {
    public boolean Find(int target, int [][] array) {
        int m =  array.length,n = array[0].length;
        int bottom = m - 1,left = 0;
        while(left < n && bottom >= 0){
            if(target == array[bottom][left]) return true;
            else if(target > array[bottom][left]) left++;
            else bottom--;
        }
        return false;
    }
}

发表于 2022-05-10 15:54:56 回复(0)
讲道理,这题是中等???直接遍历就完事了python五行代码解决
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        for i in array:
            for j in i:
                if j == target:
                    return True
        return False


发表于 2022-05-01 22:33:17 回复(0)
public class Solution {
    
    /**
     * 二维数组中的查找
     * 要求空间复杂度o(m + n)
     * 思路:
     * 如果从左上角或者右下角的元素开始遍历 那么它所在的行列其他元素都是比它大或者比它小的不好舍弃
     * 所以我们选择从左下角或者右上角开始
     * 例如:从左下角开始
     * 1. 如果元素大于目标元素,那么所在行都比目标元素大行上移 舍弃一行
     * 2. 如果元素小于目标元素,那么所在列都比目标元素小 列右移舍弃一列
     * 3. 这样做到了遍历了所有元素
     * @param target
     * @param array
     * @return
     */
    public boolean Find(int target, int [][] array) {
        // 行
        int i = array.length - 1;
        // 列 列数 array[0].length
        int j = 0;
        while (i >= 0 && j < array[0].length){
            if(target == array[i][j]) return true;
            // 当前元素大于目标元素 舍弃行
            else if(target < array[i][j]) i--;
            // 当前元素小于目标元素 舍弃列
            else if(target > array[i][j]) j++;
        }
        return false;
    }
}

发表于 2022-04-30 14:48:28 回复(0)
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        # write code here
        for every_list in array:    # 遍历每个二维数组中的list
            for value in every_list:    # 遍历每个list中的元素
                if target == value:
                    return True
        return False    # 遍历完,没有查找到,返回False
发表于 2022-04-22 16:46:26 回复(0)
Java版本
public class Solution {
    /*在查找前,我们需要明白,如果我们把右上角的点当做一棵树的根节点,
    那么在右上角左边的点(同一行的点)则比该点小, 在右上角下面的点(同一列的点)则比该点大,
    其实在数组中每个节点都有这样的规律,那么该数组查找就类似于二叉查找树的查找*/
    
    public boolean Find(int target, int [][] array) {
        int row = 0, col = array[0].length-1; //首先从数组右上角进行查找(左下角也行)
        
        while(col>=0 && row<=array.length-1){
            if(target<array[row][col]){ //如果比他小,则往左边去查找
                col--;
            }else if(target>array[row][col]){ //如果比它大,则往下面去查找
                row++;
            }else{
                return true;
            }
        }
        return false;
    }
}


发表于 2022-04-16 21:25:29 回复(0)
我是直接用includes判断二位数组是否有该元素,用some在找到元素之后自动退出循环
let flag = array.some((value) => {
        return value.includes(target)
    });
    return flag;


发表于 2021-08-09 21:07:03 回复(0)
public class Solution {
    
    // 二分法
    // 时间复杂度: O(m+n)
    // 空间复杂度: O(1)
    public boolean Find(int target, int[][] array) {
        if (array == null || array.length == 0) {
            return false;
        }

        // 从右上角元素val开始
        // 若target==val, 返回true
        // 若target>val, val下移一行
        // 若target<val, val左移一列
        int i = 0, j = array[0].length - 1, val;
        while (i < array.length && j >= 0) {
            val = array[i][j];
            System.out.println(val);
            if (target == val) {
                return true;
            } else if (target > val) {
                i++;
                // System.out.println("i = " + i + ", j = "  + j);
            } else {
                j--;
                // System.out.println("i = " + i + ", j = "  + j);
            }
        }

        // 循环走完还没找到, 返回false
        return false;
    }

    // 也可以从左下角元素val开始
    // 若target==val, 返回true
    // 若target>val, j++
    // 若target<val, i--

    // 注意: 千万不能从左上角或右下角元素开始!!
    // 对于左上角而言, 它下边和右边的元素都大于target, 是无法缩小target范围的
    // 对于右下角而言, 它上边和左边的元素都小于target, 是无法缩小target范围的
}

发表于 2021-08-04 10:32:58 回复(0)
为什么始终有一个测试用例过不去啊。。就算是暴力搜索也不行。。。
发表于 2021-07-31 22:40:44 回复(2)
public class Solution {
    public boolean Find(int target, int [][] array) {
        //二维数组同样采用二分查找的思想
        int m=array.length;//行
        int n=array[0].length;//列
        int i=0;
        int j=n-1;
        while(i>=0 && i<m && j>=0 && j<n){
            int mid=array[i][j];
            if(target<mid){
                j--;
            }else if(target>mid){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }
}

发表于 2021-07-27 16:06:31 回复(3)
public class Solution {
    public boolean Find(int target, int [][] array) {
        boolean flag = false;
        for (int[] ints : array) {
            for (int i = 0; i < ints.length; i++) {
                if(target == ints[i]){
                    flag = true;
                    return flag;
                }
            }
        }
        return flag;
    }
}
发表于 2021-04-26 14:07:49 回复(0)
//标准库很实用
class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        
        bool bfind = false;
        for(int i=0; i<array.size(); i++)
        {
            if(count(array[i].begin(), array[i].end(), target))
            {
                bfind = true;
                break;
            }
        }
        return bfind;
    }
};

发表于 2021-04-25 22:29:27 回复(0)