首页 > 试题广场 >

二维数组中的查找

[编程题]二维数组中的查找
  • 热度指数：2367262 时间限制：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
算法知识视频讲解
添加回答
推荐
徘徊的路人甲头像 徘徊的路人甲 
/* 思路
* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，
* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时，上移
*/

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)
Javascript
"旗开得胜"头像 "旗开得胜" 
function Find(target, array)
{
    // write code here
    for (var i = 0; i < array.length; i++) {
        for (var j = 0; j < array[i].length; j++) {
            if (array[i][j] == target) {
                return true;
            }
        }
    }
    return false;
}
module.exports = {
    Find : Find
};

发表于 2022-09-01 12:46:26 回复(0)
Javascript
牛客985090669号头像 牛客985090669号
function Find(target, array)
{
    // write code here
    let arr = array
    let newArray = [].concat.apply([],arr)

    return newArray.findIndex(item=>item === target) > -1 ? true : false
}
发表于 2022-07-15 18:25:39 回复(0)
Javascript
不浪了头像 不浪了 
function Find(target, array)
{
    // 投机取巧
    return array.flat(1).includes(target);
    
}
module.exports = {
    Find : Find
};

发表于 2022-05-18 22:14:16 回复(0)
Javascript
纯海之蓝头像 纯海之蓝
不考虑双指针的话
return array.flat(array.length).includes(target)
考虑双指针的话，以二维数组的右上角作为标志，如果目标大于右上角的数值，那么说明当前行的数据均小于目标，所以需要向下一行，如果目标数值小于右上角的数值，说明当前列的数据均大于目标，需要向前一列
function Find(target, array)
{
    // write code here
    if(array.length === 0 || array[0].length === 0) return false
      if(target< array[0][0] || target > array[array.length-1][array[0].length] -1) return false
      let x = 0
      let y = array[0].length -1
      while(x<= array.length-1 && y>=0) {
        if(array[x][y] > target) {
          y--
        } else if(array[x][y] < target) {
          x++
        } else {
          return true
        }
      }
      return false
}
发表于 2022-04-29 10:33:39 回复(0)
Javascript
summer_swilder头像 summer_swilder
function Find(target, array)
{
    let newArr = [];
    array.forEach(item => {
        newArr = [...newArr, ...item];
    })
    
    if (newArr.indexOf(target) == -1) {
        return false;
    } else {
        return true;
    }
}
module.exports = {
    Find : Find
};
发表于 2022-04-23 13:07:41 回复(0)
Javascript
牛客960054414号头像 牛客960054414号
二维数组将其扁平化，然后再排序或者不排序，再使用二分查找为什么不行
发表于 2022-04-10 10:43:38 回复(0)
Javascript
Danae2头像 Danae2
function Find(target, array)
{
    let low = 0,hight=0,mid,result=false;
    for(let i=0;i<array.length;i++){
        hight=array[i].length-1
        low=0
        mid=0
        while(low<hight){
            mid=Math.floor((low+hight)/2)
            if(array[i][mid]<target){
                low = mid +1
            } else {
                hight = mid
            }
        }  
        result = array[i][hight]===target
        if(result) return result
    };
    return result;
}
发表于 2022-02-24 16:29:02 回复(0)
Javascript
我有一只小毛驴201807031703918头像 我有一只小毛驴201807031703918 
function Find(target, array)
{
    return FindHelper(target, array,0, array[0].length-1);
    function FindHelper(target, array, rows, cols) {
        if (rows > array.length-1 || cols < 0) return false;
        if (target === array[rows][cols]) return true;
        if (target < array[rows][cols]) return FindHelper(target, array, rows, cols - 1);
        if (target > array[rows][cols]) return FindHelper(target, array, rows + 1, cols);
    }
}

发表于 2021-08-15 20:43:23 回复(0)
JavaScript
牛客397479434号头像 牛客397479434号
js  
   return array.some((item) => item.includes(target));


发表于 2021-08-09 21:44:02 回复(0)
JavaScript
别卷啦！头像 别卷啦！
因为矩阵的特殊性，所以先从第一列最后一行开始比较，小于则向上查找，大于则向后查找 
function Find(target, array)
{
    // write code here
    let m = array.length;
    let n = array[0].length;
    let i = 0;
    let 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;
}

发表于 2021-07-05 10:35:16 回复(0)
JavaScript
你有尾巴吗头像 你有尾巴吗 
function Find(target, array)
{
       return array.some(arr=>arr.includes(target) )
}

发表于 2021-06-23 17:04:18 回复(0)
JavaScript
牛客558575581号头像 牛客558575581号
function Find(target, array)
{
 let arr=[];
    for(let i of array){
        arr.push(...i)
    }
    return arr.includes(target);
}
用 for...of遍历可以直接取出对应属性值 for...in遍历数组获取的是索引值, 拿到属性值之后用扩展运算符将获取的4个数组展开成参数 再运用数组的push方法，将参数添加进新数组。
发表于 2021-06-09 14:26:04 回复(0)
JavaScript
苗条的海王sp到手了头像 苗条的海王sp到手了
看看我的把，哪有那么复杂，换种思路随便写
function Find(target, array)
{
    // write code here
    let c = []
    for(let key in array){
        c.push(...array[key])
    }
    return c.includes(target)
}

发表于 2021-05-28 23:00:38 回复(0)
JavaScript
青山依旧i头像 青山依旧i 
// 转为一位数组进行判断。
function Find(target, array)
{
    let arr = [];
    for(let i in array){
        arr = arr.concat(array[i]);
    }
    return arr.includes(target);
}


发表于 2021-05-14 15:19:39 回复(0)
JavaScript
LeellllllllJ头像 LeellllllllJ 
  //利用矩阵角点的特点,右上角的点为第一行的最大值,为最后一列的最小值
    //所以在判断的时候只需判断与右上角点的关系,小就往左移,大就往下移


    //判断是否为空
  if(matrix.length === 0 || matrix[0].length === 0){
    return false
  }
  
  // 分别取二维矩阵的长宽
  let m = matrix.length;//行数
  let n = matrix[0].length;//列数

  let row = 0;
  let col = n - 1;

  //如果target小于右上角，说明 最后一列均大于它，列数--
  // 如果target大于右上角，说明第一列均小于它， 行数--
  while(row < m && col >= 0){
    if(matrix[row][col] > target){
      col--;
    }else if(matrix[row][col] < target){
      row++;
    }else{
      return true
    }
  }
  return false

发表于 2021-05-14 15:03:47 回复(0)
JavaScript
Panpanpie头像 Panpanpie 
function Find(target, array) {
    var row = array.length;
    var col = array[0].length;
    var flag = false;
    for (var i = 0; i < row; i++) { // 逐行遍历
        if (array[i][0] > target) { // 行首元素大于目标值结束数组遍历
            break;
        }
        for (var j = 0; j < col; j++) { // 逐（行内）元素遍历
            if (array[i][j] > target) { // 存在元素大于目标值结束本行遍历
                break;
            } else if (array[i][j] == target) {   // 存在目标值结束遍历
                flag = true;
                break;
            }
        }
        if (flag == true) {
            break;
        }
    }
    return flag;
}
发表于 2021-04-21 16:36:39 回复(0)
JavaScript
隋明旭头像 隋明旭
function Find(target, array)
{
 // write code here
    return array.some(v =>{
        if(v.indexOf(target) != -1)
               return true
    });
}
发表于 2021-04-13 17:17:10 回复(0)
JavaScript
lufeng_头像 lufeng_ 
// 考察，数组拍平，判断是否在数组中
function Find(target, array)
{
    let arr = array.reduce((prev, cur) => {
        return prev.concat(cur)
    }, [])
    return arr.includes(target);
}

发表于 2021-03-31 11:07:00 回复(0)
提交观点

问题信息

数组
来自：2015年度信息化技能...
难度：
100条回答 1521145浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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