首页 > 试题广场 > 二维数组中的查找

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

热度指数：920939 时间限制：1秒空间限制：32768K
算法知识视频讲解

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

算法知识视频讲解

2385个回答

添加回答

Java

Tommey周

个人建议用我的解题思路：

列如一个二维数组 int arr[][] = {{1，2，9}，{3，4，10}，{5，7，12}}

我们查找二维数组里面是否存在 7

我们可以先从最右边算起拿9和7作比较，显然9后面的一列都不符合，在计算倒数第二列2小于7，那么选择在第倒数第二列中查看是否有7，参考代码如下

public class Test{

public static boolean(int[][] arr, int find){

int rows = arr.length;//一共有多少行

int cols = arr[0].length//第一行的个数

int i = 0; //第一行第一个数的下标

int j = cols - 1;//第一行最后一个下标

while(i<rows&&j>=0){

if(arr[i][j]>find){

j--;

continue;

}

else if(arr[i][j]<find){

i++;

continue;

}

else{

renturn true;

}

return false;

}

发表于 2018-12-06 21:38:22 回复(0)

更多回答

推荐

徘徊的路人甲

/* 思路

* 矩阵是有序的

查看全部

编辑于 2015-06-18 16:50:07 回复(161)

楚云天

两种思路
一种是：
把每一行看成有序递增的数组，
利用二分查找，
通过遍历每一行得到答案，
时间复杂度是nlogn
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;

    }
}

另外一种思路是：
利用二维数组由上到下，由左到右递增的规律，
那么选取右上角或者左下角的元素a[row][col]与target进行比较，
当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,
即col--；
当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,
即row++；
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;

    }
}

编辑于 2015-12-21 22:58:19 回复(38)

Python

scaucrj

从左下角元素往上查找，右边元素是比这个元素大，上边是的元素比这个元素小。于是，target比这个元素小就往上找，比这个元素大就往右找。如果出了边界，则说明二维数组中不存在target元素。

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

编辑于 2017-07-20 17:04:43 回复(14)

风铃i

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

发表于 2018-04-04 14:34:31 回复(8)

菩提旭光

最佳答案：没有之一。思路：首先我们选择从左下角开始搜寻，(为什么不从左上角开始搜寻，左上角向右和向下都是递增，那么对于一个点，对于向右和向下会产生一个岔路；如果我们选择从左下脚开始搜寻的话，如果大于就向右，如果小于就向下)。

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;

}

发表于 2015-08-26 14:14:12 回复(59)

小公举~

这个编译器特别蛋疼。。。

发表于 2015-09-17 20:59:12 回复(17)

这是小楠的微博

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

答案正确:恭喜！您提交的程序通过了所有的测试用例

左下角开始，遇大右移，遇小上移，直到超过边界都没找到，得false。否则得true。

编辑于 2015-09-18 23:44:17 回复(15)

董可伦

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

发表于 2015-08-12 09:57:56 回复(11)

ziyunmuxu

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

发表于 2015-09-18 16:05:03 回复(0)

Python

华科平凡

# -*- 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

发表于 2017-09-08 22:45:58 回复(0)

喜牛牛

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

//方法简单,代码少

发表于 2016-03-17 19:50:56 回复(17)

JavaScript

牛客488968号

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

发表于 2017-09-11 17:18:55 回复(0)

OMGZui

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

发表于 2017-05-18 22:29:29 回复(3)

冒菜。

测试用例不是数组在前面，要查找的数字在后面吗，看不懂是什么意思。。

测试用例:

16,[[]]

对应输出应该为:

false

发表于 2015-10-01 09:46:29 回复(9)

牛客-120抢救中心

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

发表于 2018-07-30 20:02:01 回复(0)

Joe_liu

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;
	}
};
从左下角或者右上角开始搜索均可

发表于 2015-08-28 09:54:52 回复(1)

HowieLee

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 head = 0;
            int tail = array[i].length-1;
            while(head<=tail){
                int mid = (head+tail)/2;
                if(target < array[i][mid]){
                    tail = mid - 1;
                }
                else if(target > array[i][mid]){
                    head = mid + 1;
                }
                else
                    return true;
            }
        }
        return false;        
    }
}

发表于 2018-07-23 08:42:55 回复(0)

C/C++

桥deer

从右上角开始，因为左边比它小，右边比它大,如果当前值比target小就行数+1，如果当前值比target小就列数-1，最后保证不越界就好。

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

发表于 2017-04-14 11:23:03 回复(0)

Java

瑰意骑行

看了很多解法都把二维数组当做矩阵，根本没考虑不等长的问题（好吧，按题意“每一列都按照从上到下递增的顺序排序”，应该不用考虑）；
例如以下测试案例，那些解法就过不了：
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;
    }
}

当然，对每一行进行二分查找或者暴力搜索不存在此问题；

编辑于 2017-07-10 15:08:21 回复(5)

SunSu

以有序矩阵的左下角或者右上角为起点。

这样比较可以根据大小确定遍历的方向。

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

编辑于 2018-07-31 12:54:56 回复(0)

专业陪跑

思路：

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;

}

发表于 2017-09-24 00:18:12 回复(0)