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

43个回答

添加回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(158)
function Find(target, array) {
    var row=array.length;
    var col=array[0].length;
     //之前找原因找了很久,原来是少了for的分号,要记得即使后面没有也需要分号
    for(var i=0,j=col-1; i<row && j>=0;) { 
        var ref=array[i][j];
        if(ref===target) {
            return true;
        } else if(ref>target) {
            j--;
        } else{
            i++;
        }
    };
    return false;
}

发表于 2019-01-14 22:18:48 回复(0)
二维数组arr[i][j]
将二维数组看作平面坐标系
j代表x坐标
i代表y坐标
从左下角(0,arr.length-1)开始比较:
目标值大于坐标值---x坐标+1
目标值小雨坐标值---y坐标-1

    function Find(target, array) {
      let i = array.length - 1; // y坐标
      let j = 0; // x坐标
      return compare(target, array, i, j);
    }

    function compare(target, array, i, j) {
      if (array[i] === undefined || array[i][j] === undefined) {
        return false;
      }
      const temp = array[i][j];
      if (target === temp) {
        return true;
      }
      else if (target > temp) {
        return compare(target, array, i, j+1);
      }
      else if (target < temp) {
        return compare(target, array, i-1, j);
      }
    }

发表于 2019-01-07 00:27:22 回复(0)
javascript 版本

两种实现方法
function Find(target, array)
{
    // write code here
    for(var i of array) {
        if (i.indexOf(target) > -1) {
            return true;
        }
    }
}

function Find(target, array)
{
    // write code here
    return array.some(arr=>arr.some(item => item === target));
}


发表于 2018-11-15 10:30:07 回复(0)
function Find(target, array)
{
    let len = array.length
    for(let i = 0; i < len; i++){
        let res = array[i].some( res => res == target)
        if(res){
            return res
        }
    }
}

暴力遍历
发表于 2018-11-12 10:02:52 回复(0)
function Find(target, array){
const rows = array.length;
const columns = array[0].length;
let row = 0;
let column = columns - 1;
while(row < rows && column >= 0) {
let val = array[row][column];
if(val === target) {
return true;
} else if (val > target) {
column--;
} else {
row++;
}
}
return false;
}
发表于 2018-10-05 16:21:26 回复(0)
我犯了一个常识性错误,给大家看,首先是错误代码:
function Find(target, array)
{

    
    var i = 0;
    var j = array[i].length-1;
    while(i<=array.length-1 && j>=0){
        if(array[i][j] == target)
            return true
        else if(target<array[i][j])
            j--;
        else(target>array[i][j])
            i++
    }  
}

下面是正确的:
function Find(target, array)
{

    
    var i = 0;
    var j = array[i].length-1;
    while(i<=array.length-1 && j>=0){
        if(array[i][j] == target)
            return true
        else if(target<array[i][j])
            j--;
        else if(target>array[i][j])
            i++
    }  
}

错误地方标出来了哈

发表于 2018-09-26 17:47:24 回复(0)
function Find(target, array) {
    for (var i = array.length - 1;i >= 0;i--) {
        for (var j = array[i].length - 1; j >= 0; j--) {
            if (array[i][j] === target) {
                return true;
            }
        }
    }
    return false;
}
发表于 2018-09-02 11:37:42 回复(0)


function Find(target, array)
{
var le = array.length;
var arr = [];
var flag = false;
for (var i = 0; i < le;i++) {
    var ite = array[i].some(function(item, index , array) {
        return item === target // 在每个一位数组里找对应的数字,有则返回true
    });
    arr.push(ite); //保存每个一位数组的结果
};

for (var j= 0; j < le; j++) {
if(arr[j] === true) { 遍历保存的结果
    flag = true ;
}

}
return flag;
}

发表于 2018-08-15 10:25:20 回复(0)
function Find(target, array)
{
    var arr = array.join(',').split(',');
    return arr.some((item=>{
        return item == target;
    }))
}
js了解一下?
发表于 2018-08-13 16:45:29 回复(0)
function Find(target, array)
{
   return array.join(",").split(",").indexOf(target.toString()) > -1
}

发表于 2018-07-31 09:42:26 回复(0)
從最左下角的元素開始比較,如果該元素比target大,則 column index 往右移, 若相反,則 row index 往上移。

function Find(target, array) {     
     let i = array.length - 1,  j = 0;
    while (i >= 0 && j < array.length) {
        let cur = array[i][j];
        if (cur === target) {
            return true;
        } else if (cur > target) {
            i--;
        } else {
            j++;
        }
    }
    return false;
}
发表于 2018-07-11 09:49:35 回复(0)
/*
* 思路参看推荐 从左下角开始比较是最快的,我的代码使用while循环更简洁
*/
function Find(target, array)
{
    // write code here
    let i = array.length - 1;
    let j = 0;
    while(i >= 0 && j < array[0].length){
        if(target == array[i][j]){
            return true;
        }else if(target > array[i][j]){
            j++;
        }else{
            i--;
        }
    }
    return false;
}
module.exports = {
    Find : Find
};

发表于 2018-06-13 10:37:16 回复(0)

没有看到分享JavaScript代码的,我分享一个,思路还是最高票的那位同学的,相当简洁

function Find(target, array)
{
    // write code here
    var col_len = array.length;
    var row_len = array[0].length;
    var col = col_len - 1;
    var row = 0;
    while (col >= 0 && row < row_len) {
        if (target > array[row][col]) {
            row++;
        } else if (target < array[row][col]) {
            col--;
        } else {
            return true;
        }
    }
    return false;
}

编辑于 2018-06-11 23:15:20 回复(0)
function Find(target, array)
{     //能确定的就是第一个数一定是最小的,所以可以先直接判断     //然后依次(因为无法确定大小)遍历每一行     //在每一行中首先用二分查找判断,然后再向左或者向右移比较,会节省一点的时间     if(target<array[0][0]){         return false;     }else{         for(var i in array){             var arr = array[i];             if(target<arr[0] || target>arr[arr.length-1]){                 continue ;             }else{                 var temp = Math.ceil(arr.length);                 if(target == arr[temp]){                     return true;                 }else if(target > arr[temp]){                     do{                         temp ++;                         if(target == arr[temp]){                             return true;                         }                     }while(temp < arr.length);                 }else{                     do{                         temp --;                         if(target == arr[temp]){                             return true;                         }                     }while(temp>-1);                          }             }         }     }     return false; }

编辑于 2018-05-24 12:41:19 回复(0)
function Find(target, array)
{
    // write code here
    if(array !== null){
        var row = 0;
        var column = array[0].length-1;
        while(column >= 0 && row< array.length){
            var tempt = array[row][column];
            if(target === tempt){
                return true;
            }else if(target > tempt){
                row++;
            }else{
                column--;
            }
        }
    }
    return false
}

发表于 2018-05-07 08:33:26 回复(0)
从右上角取值:
function Find(target, array) {
    // write code here
    let result = false;
    if (array.length === 0) {
        return result;
    }
    // 从右上角取值
    let row = 0; // 行的长度
    let column = array[0].length - 1; // 列的长度
    while (row < array[0].length && column >= 0) {
        if (target === array[row][column]) {
            result = true;
            break;
        }
        if (target > array[row][column]) {
            ++row;
        } else if (target < array[row][column]) {
            --column;
        }
    }
   
    return result;
}
发表于 2018-05-04 14:12:45 回复(0)
function Find(target, array)
{
    var i = 0, j = array[0].length-1;
    while(i < array.length && j >= 0){
        // console.log(array[i][j]);
        if(array[i][j] === target){
            return true;
        }else if(array[i][j] > target){
            --j;
        }else{
            ++i;
        }
    }
    return false;
}
编辑于 2018-04-21 00:46:50 回复(0)
先选择矩阵的第一列数据做比较,从下往上,若target大于当前行第一个值,那么继续往上找,若target小于当前行第一个值,则使用二分法在当前行中查找是否满足条件,若满足则返回,若不满足则继续往上找 直到行等于第一行,或满足条件为止,

[  }

编辑于 2018-04-20 10:59:48 回复(2)
思路:
从第一行开始对比,可以得到每一行从哪个值开始大于target,记录下那个值。
然后就可以接下来的哪一行的最大长度不会大于第一行的那个值,而且也把这行从哪个值开始大于target,记录下来。
依次接下来的每一行其实检查的长度都回逐渐减少。
发表于 2018-04-02 10:15:33 回复(0)
根据二维数组的结构,从左到右递增,从上到下递归,选择一个比较适合的切入点,进行数组遍历,比较。这个选择的切入点需要满足,当要查找的数据与它作比较时,有唯一的出路可走,如当要查找的数据大于这个切入点时,下面该往哪里继续查找,不能同时几条路都可以选择,那判断起来就麻烦了。这里我们以第n行第1列数据为切入点,即二维数组最左下角的元素,这样当要查找的数据大于该切入点时,直接j++向右进行遍历,如果要查找的数据小于该切入点时,直接i--向上进行遍历,否则,那切入点即为要查找的数据,如此循环,直到找到为止。点需要满足,当要查找的数据与它作比较时,有唯一的出路可走,如当要查找的数据大于这个切入点时,下面该往哪里继续查找,不能同时几条路都可以选择,那判断起来就麻烦了。这里我们以第n行第1列数据为切入点,即二维数组最左下角的元素,这样当要查找的数据大于该切入点时,直接j++向右进行遍历,如果要查找的数据小于该切入点时,直接i--向上进行遍历,否则,那切入点即为要查找的数据,如此循环,直到找到为止。
比较。这个选择的切入点需要满足,当要查找的数据与它作比较时,有唯一的出路可走,如当要查找的数据大于这个切入点时,
的数据大于这个切入点时,下面该往哪里继续查找,不能同时几条路都可以选择,那判断起来就麻烦了。
了。这里我们以第n行第1列数据为切入点,即二维数组最左下角的元素,这样当要查找的数据大于该切入点时,直接j++向右进行遍历,如果要查找的数据小于该切入点时,直接i--向上进行遍历
,否则,那切入点即为要查找的数据,如此循环,直到找到为止。
function Find(target, array) 
{
    var row=array.length;
    if(row==0){
        return false;
   }
    var col=array[0].length;
    var i=row-1,j=0;  //以最后一行第一列为基准
    while(i>=0&&j<col){ //循环
        if(array[i][j]<target){ //待查找值大,继续向右查找
            j++;
        }else if(array[i][j]>target){ //待查找值小,向上继续查找
            i--;
        }else{   //找到
            return true;
        }
    }

发表于 2018-03-22 00:11:30 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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

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