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

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 回复(218)
遍历二维数组,这时每个元素是一个一维数组,在用Array.indexOf判断一维数组中是否包含目标元素,若包含则返回true,跳出循环;若不包含则continue跳出本次循环,继续查找下一个一维数组是否包含目标元素。
function Find(target, array)
{
    // write code here
    let length = array.length;
    let flag = false;
    for(let i=0; i<length; i++) {
        let firstLevelArr = array[i];
        if(firstLevelArr.indexOf(target) > -1) {
            return flag = true;
        } else {
            continue;
        }
    }
    
    return flag;
}


发表于 2019-10-26 16:02:27 回复(0)
JavaScript版本:
从右上角开始查找比对。
若value=target,返回他true;若value>target,剔除最后一列继续查找;若value<target,剔除第一行继续查找···。
需注意边界条件的处理。代码如下:
function Find(target, array) {
    const end = array.length;
    let row = 0;
    let col = array[0].length - 1;
    while (true) {
        if (row === end || col === -1) {
            return false;
        }
        const value = array[row][col];
        if (value === target) {
            return true;
        } else if (value > target) {
            --col;
        } else {
            ++row;
        }
    }
}


发表于 2019-10-14 09:57:51 回复(0)

function Find(target, array)
{
    // write code here
    for(var i = 0; i < array.length;i++){
        if(array[i].indexOf(target) != -1){
            return true;
        }
        if(i == array.length -1){
            return false;
        }
    }
}
indexOf 来查找
发表于 2019-09-19 13:44:45 回复(0)
function Find(target, array) {
    let index = array.flat().indexOf(target);
    if (index < 0)
      return false;
    return true;
}

// 这种解法在线提交无法通过,0%,可能因为编译的原因,也可能是数组降维后长度越界。

发表于 2019-09-13 20:27:46 回复(0)
使用JS实现的方法蛮多的,这边提供一种思路
return Array.from(new Set([].concat.apply([],array))).indexOf(target) == -1 ? false : true;
发表于 2019-09-08 16:07:23 回复(0)
function Find(target, array)
{
    return array.flat().includes(target)
}
Find(12, [[1,5,9,13],[2,6,10,14],[3,7,11,15],[4,8,12,16]])
js不让过?
编辑于 2019-09-03 17:37:43 回复(0)
function Find(target, array)
{
    var str=array.toString().split(',')
    var flag=false
    for(var i=0;i<str.length;i++){
        if(parseInt(str[i])==target){
            flag= true
        }
    }
   return flag
    // write code here
}
发表于 2019-09-02 14:48:27 回复(0)
function Find(target, array)
{
    for (let i = 0; i < array.length; i++) {
        let str = array[i].join(',');
        if (str.indexOf(',' + target) > -1) {
            return true
        }
    }
    return false;
}
js算法了解一下?将里面的数组变成字符串再去找,降低复杂度
发表于 2019-09-02 10:00:42 回复(0)
    function Find(target, array) {
		let length = array.length
		let itemLen = array[0].length

		if (length === 0 || itemLen === 0) {
			return false
		}

		return judgeTarget(target, array, length, itemLen, 0)
	}

	function judgeTarget(target, array, length, itemLen, index = 0) {
		// index为行 
		if (index >= length) {
			return false
		}
		if (itemLen <= 0) {
			return false
		}

		if (target === array[index][itemLen - 1]) {
			return true
		}
		if (target < array[index][itemLen - 1]) {
			return judgeTarget(target, array, length, itemLen - 1, index)
		} else {
			return judgeTarget(target, array, length, itemLen, index + 1)
		}
	}


从左上角开始判断分析  递归判断分析。 这个思路调试一遍就能清楚
编辑于 2019-08-26 13:55:22 回复(0)
js版本
function Find(target, array)
{
//从左下角寻找,先判断是否相等,target大往右走,小了往上走
        var cols = array[0].length;
        var rows = array.length;
        var i = rows-1;var j = 0;
        for(;(i>=0 && j<=cols); ){
            if(target==array[i][j]){
                return true;
            }
            if(target>array[i][j]){
                j=j+1;
                continue;
            }else{
                i=i-1;
                continue
            }

        }
        return false;
}


发表于 2019-08-23 14:47:15 回复(0)
js 实现,思路前面的大佬说的很明白了
function Find(target, array)
{
  let rows = array.length;
  let cols = array[0].length;
    if(rows == 0){
        return false
    }
    if(cols == 0){
        return false
    }
    let row = rows - 1;
    let col = 0;
    while(row>=0&&col<cols){
        if(target > array[row][col]){
            col++;
        }
        else if(target < array[row][col]){
            row--;
        }
        else{
            return true
        }
    }
    return false
}

发表于 2019-08-22 15:02:55 回复(0)
function Find(target, array)
{
    var arrlen = array.length;
    for (var i = 0; i< arrlen; i++) {
        var lineArr = array[i];
        var lineStart = lineArr[0];
        var lineEnd = lineArr[lineArr.length - 1];
        if (target >= lineStart && target <= lineEnd) {
            for (var j = 0; j < lineArr.length; j++) {
                if (lineArr[j] === target) {
                    return true;
                }
            }
        }
    }
    
    return false;
}

发表于 2019-07-23 17:36:06 回复(0)
//确定元素在那一行
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)