[编程题]二维数组中的查找

# 41个回答

`/* 思路`
`* 矩阵是有序的`
查看全部

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));
}

```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
}
}
}

```

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;
}

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++
}
}

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;
}

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;
}

function Find(target, array)
{
var arr = array.join(',').split(',');
return arr.some((item=>{
return item == target;
}))
}
js了解一下？

```function Find(target, array)
{
return array.join(",").split(",").indexOf(target.toString()) > -1
}
```

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;
}

```/*
* 思路参看推荐 从左下角开始比较是最快的，我的代码使用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
};
```

```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;
}

```

```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;
}
```

```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
}
```

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;
}

```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;
}
```

`[  }`

```
根据二维数组的结构，从左到右递增，从上到下递归，选择一个比较适合的切入点，进行数组遍历，比较。这个选择的切入点需要满足，当要查找的数据与它作比较时，有唯一的出路可走，如当要查找的数据大于这个切入点时，下面该往哪里继续查找，不能同时几条路都可以选择，那判断起来就麻烦了。这里我们以第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;

}

}

```

```

//方法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;

}

```

```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);
}```

41条回答 586119浏览

# 通过挑战的用户

• 2018-12-13 21:46:42
• 2018-12-13 21:46:34
• 2018-12-13 21:45:41
• 2018-12-13 21:39:15
• 2018-12-13 21:39:13

# 相关试题

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题

• 公司地址：北京市朝阳区大屯路东金泉时代3-2708北京牛客科技有限公司