首页 > 试题广场 > 二维数组中的查找
[编程题]二维数组中的查找
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
推荐
/* 思路
* 矩阵是有序的,从左下角来看,向上数字递减,向右数字递增,
* 因此从左下角开始查找,当要查找数字比左下角数字大时。右移
* 要查找数字比左下角数字小时,上移
*/

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 回复(199)
//确定元素在那一行
var findLine = function(array, element) {
    //二维数组的长度
    var len = array.length - 1
    //一维数组的长度
    var length = array[0].length - 1
    var index = -1
    for (var i = 0; i < len; i++) {
          //找到每一行末尾的数字
          var arr = array[i][length]
          if(element <= arr) {
             index = i
      }
    }
    //找到index就是i,如果找不到,index就返回默认值 -1
    return index
}

//确定行后,开始寻找
var find = function(array, element) {
    var index = findLine(array, element)
    if(index == -1) {
        console.log("没有找到",element)
        return
    } else {
      //找到one所在的行具***置
        var findOne = array[index].indexOf(element)
        if(findOne == -1) {
        console.log("没有找到",element)
        } else {
        console.log("找到",element)
        }
    }
}
发表于 2019-07-12 10:31:40 回复(0)
function Find(target, array) {  
  let flag = false;
  for (let i = 0; i < array.length; i++) {
    if (array[i].indexOf(target) !== -1) {
      flag = true;
      break;
    }
  }
  return flag;
}

通过数组的 indexOf 方法去查找
编辑于 2019-07-08 23:03:25 回复(0)
let res = false;
    for(i=0;i<array.length;i++){
        for(j=0;j<array[i].length;j++){
            if(array[i][j]==target)
                res=true;
        }
    }
    return res;
发表于 2019-06-22 10:56:38 回复(0)
思路:
    从左到右递增,从上到下递增。每行都是从左到右递增,那在每一行中最后一个数字肯定是最大的;可以那target从右往左比,如果target比最右的还大,则直接到下一行;如果target比它小,则再跟前一个比较.......
function Find(target, array)
{
    var rowLen = array.length,
        colIndex = array[0].length -1,
        flag = false;
    for(var i = 0; i < rowLen; i++) {
        while (colIndex >=0 && target < array[i][colIndex]) {
            colIndex--;
        }
        if(array[i][colIndex]===target){
            flag = true;
            break;
        }
    }
    return flag;
}
发表于 2019-04-03 15:34:24 回复(0)
我是用javaScript做的,不通过,检查了一会,觉得逻辑没啥问题,有大佬指导一下吗
发表于 2019-03-28 10:23:30 回复(0)
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 回复(1)
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)