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

39个回答

添加回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(150)
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)
//方法1、双重for循环遍历
function Find(target, array) {
var has = false;
for(var i = 0; i < array.length; i++) {
for(var j = 0; j < array[0].length; j++) {
if(target == array[i][j]) {
has = true;
break;
}
}
}
return has;
}
//方法2、二分法查找
function halfSearch(target, arr) {
var has = false;
var len = arr.length;
var low = 0;
var high = len - 1;
var mid;
if(target < arr[0] || target > arr[high]) { //边界检查
return has;
}
while(low <= high) {
mid = Math.floor((low + high) / 2);
if(target === arr[mid]) {
has = true;
break;
} else if(target > arr[mid]) {
low++;
} else if(target < arr[mid]) {
high--;
}
}
return has;
}
function Find(target, array) {
var has = false;
var lenx = array.length;
var leny = array[0].length;
if(target < array[0][0] || target > array[lenx-1][leny-1]) { //边界检查
return has;
}
for(var i = 0; i < lenx; i++) {
has = halfSearch(target, array[i]);
if(has) {
return has;
}
}
return has;
}
//方法3、最佳答案:从左下角开始,往上越来越小,往右越来越大
function Find(target, array) {
var lenx = array.length;
var leny = array[0].length;
var px = lenx - 1;
var py = 0;
var has = false;
while(px >= 0 && py <= leny-1) {
if(target == array[px][py]) {
has = true;
break;
} else if(target < array[px][py]) {
px--;
} else if(target > array[px][py]) {
py++;
}
}
return has;
}

编辑于 2018-03-15 14:08:30 回复(0)
想了一种麻烦的,分成四个块,左上一定是块中最小,左下一定是最大,所以只要taget在这之间就有可能存在,于是进入更小的块递归。
function FindInSqure(target,array,left,top,right,bottom){
    let centerx = Math.floor((left+right)/2);
    let centery = Math.floor((top+bottom)/2);
    let areas = [];
    if (Math.abs(left - right)<=1 && Math.abs(top - bottom)<=1) {
        switch(target){
            case array[top][left]:
            return true;
            case array[top][right]:
            return true;
            case array[bottom][left]:
            return true;
            case array[bottom][right]:
            return true;
            default:
            return false;
        }
    }
    areas.push([left,top,centerx,centery,array[top][left],array[top][centerx],array[centery][left],array[centery][centerx]]);
    areas.push([centerx,top,right,centery,array[top][centerx],array[top][right],array[centery][centerx],array[centery][right]]);
    areas.push([left,centery,centerx,bottom,array[centery][left],array[centery][centerx],array[bottom][left],array[bottom][centerx]]);
    areas.push([centerx,centery,right,bottom,array[centery][centerx],array[centery][right],array[bottom][centerx],array[bottom][right]]);
    let ok = false;
    for (let i = 0; i < areas.length; i++) {
        let a = areas[i];
        for (let ai = 4; ai < a.length; ai++) {
            let p = a[ai];
            if (p == target) {
                return true;
            }
        }
        let start = a[4];
        let end = a[7];
        if (target>start && target<end) {
            let area = areas[i];
            if (!ok) {
                ok = FindInSqure(target,array,area[0],area[1],area[2],area[3]);
            }
        }
    }
    return ok;
}
function Find(target, array){
    if(array.length==0){
        return false;
    }
    let firstRow = array[0];
    if(firstRow.length==0){
        return false;
    }
    return FindInSqure(target,array,0,0,firstRow.length-1,array.length-1);
}

发表于 2018-02-13 02:57:05 回复(0)
function Find(target, array)
{
    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;
}


发表于 2018-01-25 12:08:31 回复(1)
// 方法1:从右上角开始
function Find(target, array){
    const rows = array.length;
    const columns = array[0].length;
    for(let row = 0 , column = columns - 1 ; row < rows && column >=0 ; ){
        if(target < array[row][column]){
           column--;
        }
        else if(target > array[row][column]){
           row++;
        }
        else if(target == array[row][column]){
           return true;
        }    
    }
    return false;
}

// 方法2:从左下角开始
function Find(target, array){
    const rows = array.length;
    const cols = array[0].length;
    for(let col = 0 , row = rows - 1 ; col < cols && row >= 0 ; ){
        if(target > array[row][col]){
            col++;
        }
        else if(target < array[row][col]){
            row--;
        }
        else if(target == array[row][col]){
            return true;
        }
    }
    return false;
}
发表于 2018-01-15 15:50:15 回复(0)

扫一扫,把题目装进口袋

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

扫描二维码,进入QQ群

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