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

# 978个回答

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

```两种思路

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;

}
}```

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 版本正确的`

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

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

```其实也可以从右上开始寻找；
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;
}
};```

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

```

16,[[]]

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

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

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

```public class Solution {
public boolean Find(int target, int [][] array) {
int m = array.length;
int n = array[0].length;
int i = m-1,j = 0;
while(true) {
if(i == -1 || j == n)    //进行边界判断，原来是在两个elseif里判断的，但是空数组的话会有异常
return false;
if(target == array[i][j])
return true;
else if(target < array[i][j])    //这里用elseif，原来用的是if，移位后array[i][j]发生改变，下面的判断有可能为true造成结果错误。使用elseif也会减少比较次数
i--;
else if(target > array[i][j])
j++;
}
}
}```

```/*
算法思想：首先选取数组中右上角的数字，如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；
如果该数字小于要查找的数字，剔除这个数字所在的行。这样每一步都可以缩小查找范围，直到找到要查找的数字，或者查找范围为空为止。*/
public class Solution {
public boolean Find(int target, int [][] array) {
//boolean found = false;
int i = 0,j = array[0].length - 1;
while(i <= array.length - 1  && j >= 0){
if(array[i][j] == target){
return true;
//break;
}else if(array[i][j] > target){
j--;
continue;
}
else{
i++;
continue;
}
}
return false;
}
}```

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

```每一行都是有序的，那么对每一行进行二分查找，时间复杂度为O(N*logN)
if (array == null || array.length == 0) {
return false;
}

int row = array.length - 1;
int col = array[0].length - 1;

int left = 0;
int right = col;
int mid = 0;

for (int i = 0; i <= row; i++) {
left = 0;
right = col;
while (left <= right) {
mid = ((right - left) >> 1) + left;
System.out.println("left====" + left);
System.out.println("right====" + right);
System.out.println("mid====" + mid);
if (left > right) {
break;
}
if (array[i][mid] == target) {
return true;
}
if (array[i][mid] > target) {
right = mid - 1;
}
if (array[i][mid] < target) {
left = mid + 1;
}
}
}
return false;

```

//以下解法二：从右上角开始走

if (array == null || array.length == 0) {
return false;
}

int row = 0;//多少行
int col = array[0].length - 1;//多少列

while (col >= 0 && row < array.length) {
if (array[row][col] == target) {
return true;
} else if (array[row][col] > target) {
col--;
} else {
row++;
}
}
return false;

《剑指OFFER》的题目只需要贴出函数部分的代码就行了，然而这并不好进行调试，还是每次都把完整的代码copy出来吧。
```/*

*/
#include <iostream>
#include <string>
using namespace std;
#include <vector>

class Solution
{
public:
bool Find(int target, vector<vector<int> > array)
{
int row=0,column;
int rows =    array.size();                   //行数
int columns = array[0].size();                //列数
bool found = false;
column = columns-1;
if(rows>0 && columns>0)                       //非“零”矩阵
{
while(row<rows && column>=0)                //判断是否越界
{
if(array[row][column]==target)
{
found = true;break;
}
else if(array[row][column]>target)
{
column = column-1;
continue;
}
else if(array[row][column]<target)
{
row = row+1;
}
}
}
cout<<found<<endl;
return found;
}
};

int main()
{
int  M=4;
int  N=4;
vector<vector<int> > Matrix(4);                     //注意中间的空格
cout<<Matrix.size()<<endl;
for(int i=0;i<4;i++)
{
Matrix[i].resize(4);
}
cout<<Matrix[0].size()<<endl;
//	for(int i=0;i<4;i++)
//	{
//	 for(int j=0;j<4;j++)
//		{
//		  Matrix[i][j] = (i*j);
//		}
//	}
Matrix[0][0]= (1);Matrix[0][1]= (2);Matrix[0][2]= (8);Matrix[0][3]= (9);
Matrix[1][0]= (2);Matrix[1][1]= (4);Matrix[1][2]= (9);Matrix[1][3]= (12);
Matrix[2][0]= (4);Matrix[2][1]= (7);Matrix[2][2]= (10);Matrix[2][3]= (13);
Matrix[3][0]= (6);Matrix[3][1]= (8);Matrix[3][2]= (11);Matrix[3][3]= (15);

for(int i=0;i<=3;i++)
{
for(int j=0;j<=3;j++)
{
cout<<Matrix[i][j]<<" ";
}
cout<<endl;
}
Solution A;
A.Find(1,Matrix);
return 0;
}```

978条回答 144590浏览

# 通过挑战的用户

• 2017-07-23 01:03:43
• 2017-07-23 00:24:36
• 2017-07-23 00:02:17
• 2017-07-22 23:54:14
• 2017-07-22 23:51:54

# 相关试题

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

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

QQ群：169195721