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

```public class Solution {
public boolean Find(int target, int [][] array) {
int row = array.length;  // 行
int col = array[0].length;  // 列
if(row == 0 || col == 0){  // 二维数组中没有元素
return false;
}
if(target > array[row - 1][col - 1])
{
return false;
}
if(target < array[0][0])
{
return false;
}
int i = 0, j = col - 1;
while(j >= 0 && i <= row - 1)  // 首先将初始的数定位在 第一行的最后一个数,O(n+m)
{
if(array[i][j] == target)
{
return true;
}
else if(array[i][j] > target)
{
j--;
}
else if(array[i][j] < target)
{
i++;
}
}

return false;
}
}
```

`/* 思路`
`* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，`
`* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移`
`* 要查找数字比左下角数字小时，上移`
`*/`

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

```两种思路

public class Solution {
public boolean Find(int [][] array,int target) {

for(int i=0;i<array.length;i++){
int low=0;
int high=array[i].length-1;
while(low<=high){
int mid=(low+high)/2;
if(target>array[i][mid])
low=mid+1;
else if(target<array[i][mid])
high=mid-1;
else
return true;
}
}
return false;

}
}

public class Solution {
public boolean Find(int [][] array,int target) {
int row=0;
int col=array[0].length-1;
while(row<=array.length-1&&col>=0){
if(target==array[row][col])
return true;
else if(target>array[row][col])
row++;
else
col--;
}
return false;

}
}```

Python版本
```# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
rows = len(array) - 1
cols= len(array[0]) - 1
i = rows
j = 0
while j<=cols and i>=0:
if target<array[i][j]:
i -= 1
elif target>array[i][j]:
j += 1
else:
return True
return False```

C++版本
```class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
// array是二维数组，这里没做判空操作
int rows = array.size();
int cols = array[0].size();
int i=rows-1,j=0;//左下角元素坐标
while(i>=0 && j<cols){//使其不超出数组范围
if(target<array[i][j])
i--;//查找的元素较少，往上找
else if(target>array[i][j])
j++;//查找元素较大，往右找
else
return true;//找到
}
return false;
}
};```

Java版本
```public class Solution {
public boolean Find(int target, int [][] array) {
int rows = array.length;
int cols = array[0].length;
int i=rows-1,j=0;
while(i>=0 && j<cols){
if(target<array[i][j])
i--;
else if(target>array[i][j])
j++;
else
return true;
}
return false;
}
}```

JS了解一下
function Find(target, array)
{
return array.some(arr=>arr.some(e=>e===target))
}

public class Solution {
public boolean Find(int [][] array,int target) {
int len = array.length-1;
int i = 0;
while((len >= 0)&& (i < array[0].length)){
if(array[len][i] > target){
len--;
}else if(array[len][i] < target){
i++;
}else{
return true;
}
}
return false;
}
}

```class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
int m,n,x,y;
m = array.size();//行数
n = array[0].size();//列数
x=m-1;y=0;//坐标定在左下角
while(x>=0 && y<=n-1){
if(target<array[x][y]){
x--;//遇小上移
}
else if(target>array[x][y]){
y++;//遇大右移
}
else {
return true;
}
}
return false;
}
};```

```public class Solution {
public boolean Find(int [][] array,int target) {
int m = array.length - 1;
int i = 0;
while(m >= 0 && i < array[0].length){
if(array[m][i] > target)
m--;
else if(array[m][i] < target)
i++;
else
return true;
}

return false;
}
}```
`java 版本正确的`

```function Find(target, array) {
let lenX = array.length;
let lenY = array[0].length;
for (let i = lenX - 1, j = 0; i >= 0 && j < lenY;) {
if (target > array[i][j]) {
j++;
}else if(target < array[i][j]) {
i--;
}else {
return true
}
}
}```

```其实也可以从右上开始寻找；
class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
int row = array.size();
int col = array[0].size();
int i,j;
for (i=0,j=col-1;i<row && j>=0;)
{
if (array[i][j] == target)
{
return true;
}
if (array[i][j] > target)
{
j--;
continue;
}
if (array[i][j] < target)
{
i++;
}
}
return false;
}
};```

``````# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if not array:
return
row=len(array)
col=len(array[0])
for i in range(row):
for j in range(col):
if array[i][j]==target:
return True
return False
``````

```public class Solution {
public boolean Find(int [][] array,int target) {
for(int[] i : array){
for(int j : i){
if(j==target)return true;
}
}
return false;
}
}

//方法简单,代码少
```

``````<?php

function Find(\$target, \$array)
{
// write code here
\$rows = count(\$array);//行
\$columns = count(\$array[0]);//列
\$rs = false;
//从右上角开始，
for (\$row = 0,\$column = \$columns - 1; \$row < \$rows && \$column >= 0;) {
if(\$array[\$row][\$column] == \$target){
\$rs = true;
break;
}
if (\$array[\$row][\$column] > \$target){
//大于目标数，剔除本列
\$column--;
}
if(\$array[\$row][\$column] < \$target) {
\$row++;
}
}
return \$rs;
}
``````

16,[[]]

false

```class Solution {
public:
bool Find(vector<vector<int> > array, int target) {
int Row = array.size();
int Col = array[0].size();

for (int i = 0, j = Col-1; i < Row && j >=0;)
{
if (target > array[i][j])
i++;
else if (target < array[i][j])
j--;
else if (target == array[i][j])
return true;
}
return false;
}
};

```

```public class Solution {
public boolean Find(int target, int [][] array) {
boolean flag = false;
int x=0;
int y=0;
for(int i=0;i < array.length;i++) {
for(int j=0;j<array[i].length;j++) {
if(target==array[i][j]){
flag = true;
break;
}
}
}
if(flag) {
System.out.println("exist!"+target+",location:"+"array["+x+"]["+y+"]");
}
return flag;
}
}

```

1.如果arr数组为空，就返回false
2.如果target小于每个数组的第一个元素，返回false
3.target大于当前行的第一个元素，小于当前行最后一个元素，用二分查找，找不到下一行

public static boolean Find(int target, int [][] arr) {

for(int i=0;i<arr.length;i++){
if(arr[i].length==0)
return false;
int n=arr[i].length;
if(target<arr[i][0])
return false;
else if(target>=arr[i][0]&&target<=arr[i][n-1]){
int left=0;
int hight=arr[i].length-1;
int mid=0;
while(left<=hight){
mid=(left+hight)/2;
if(arr[i][mid]>target)
hight=mid-1;
else if(arr[i][mid]<target)
left=mid+1;
else
return true;
}
}
}
return false;

}

``````class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
int i=0;
int j=array[0].size()-1;

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

[[1,6,7,8],

[3,7,8,9],

[9,10,11,12],

[12,13,14,15]]

```

# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
h, w = len(array), len(array[0])
for i in range(min(h, w)):      # 在正方形内对角线查找
if array[i][i] == target:
return True
elif (array[i][i] > target):
for j in range(i):        # 这里可以替换成二分查找
if (array[i][j] == target or array[j][i] == target):
return True
return False
```

[[1,6,7,8],

[3,7,8,9],

[9,10,11,12],

[12,13,14,15],

[13,14,15,16],

[,18,21,22,23]]

```# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
h, w = len(array), len(array[0])
if (h==0 or w==0):
# 递归退出条件，当矩阵不可再分时候，此时为行向量，顺序查找或者二分查找
for i in range(max(h,w)):
if(target == array[i]):
return True
return False
# 如果按照方阵情况查找
for i in range(min(h, w)):      # 在正方形内对角线查找
if array[i][i] == target:
return True
elif (array[i][i] > target):
for j in range(i):        # 这里可以查找二分查找
if (array[i][j] == target or array[j][i] == target):
return True
if (h > w):    # 如果不是方阵，则递归划分成多个小方阵查找
return self.Find(target, [row[:w] for row in array[i+1:]])
else:
return self.Find(target, [row[i+1:] for row in array[:h]])

```

```public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null || array[0].length == 0){
return false;
}
for(int i = 0;i < array.length;i++){
int tail = array[i].length-1;
if(target < array[i][mid]){
tail = mid - 1;
}
else if(target > array[i][mid]){
}
else
return true;
}
}
return false;
}
}
```

target = 12；
int[][] array = {{1,2,8},{2,4,9,12},{4,7},{6,8,11,15}};

```public class Solution {

public boolean Find(int target, int [][] array) {
int r=array.length-1,c=0,maxCol=0;
for (int i=0;i<=r;i++)
if (array[i].length>maxCol)maxCol=array[i].length;//元素最多的一行，元素数量为maxCol
while (r>=0&&c<maxCol){
if (c >= array[r].length)r--; //若该行元素较少，不存在第c列元素，继续上移；
else if (array[r][c]<target)c++;
else if (array[r][c]>target)r--;
else if (array[r][c]==target)return true;
}
return false;
}
}```

# 问题信息

3227条回答 1101778浏览

# 通过挑战的用户

• 2019-10-21 12:47:45
• 2019-10-21 12:44:58
• 2019-10-21 12:44:57
• 2019-10-21 12:29:41
• 2019-10-21 12:18:34

# 相关试题

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

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