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

978个回答

添加回答
左下角考虑,判断出大小都是唯一路径;若是每一行进行二分,也是可以做,但是麻烦。
发表于 2017-07-17 19:09:16 回复(0)
更多回答
推荐
/* 思路
* 矩阵是有序的
   查看全部
编辑于 2015-06-18 16:50:07 回复(76)
两种思路
一种是:
把每一行看成有序递增的数组,
利用二分查找,
通过遍历每一行得到答案,
时间复杂度是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 回复(16)
最佳答案:没有之一。思路:首先我们选择从左下角开始搜寻,(为什么不从左上角开始搜寻,左上角向右和向下都是递增,那么对于一个点,对于向右和向下会产生一个岔路;如果我们选择从左下脚开始搜寻的话,如果大于就向右,如果小于就向下)。
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 回复(42)
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 回复(12)
这个编译器特别蛋疼。。。
发表于 2015-09-17 20:59:12 回复(2)
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 回复(8)
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 回复(10)
其实也可以从右上开始寻找;
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)
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 回复(0)
测试用例不是数组在前面,要查找的数字在后面吗,看不懂是什么意思。。
测试用例:
16,[[]]

对应输出应该为:
false


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

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

从右上角开始,因为左边比它小,右边比它大,如果当前值比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)
想了很久才想到从左下角开始遍历,思路和大家一样。自认为自己的代码比较简洁,不知道效率是是不是一样。实现的过程中也遇到几个问题,在这里贴出来分享一下。
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++;
        }
    }
}

发表于 2017-03-05 19:34:36 回复(0)
/*
	算法思想:首先选取数组中右上角的数字,如果该数字等于要查找的数字,则查找过程结束;如果该数字大于要查找的数字,剔除这个数字所在的列;
    如果该数字小于要查找的数字,剔除这个数字所在的行。这样每一步都可以缩小查找范围,直到找到要查找的数字,或者查找范围为空为止。*/
    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;
    }
}

发表于 2017-02-25 22:01:45 回复(2)
法1:从左下搜索,遇大上移,遇小右移,时间复杂度O(m+n) 法2:每行都进行二分查找,时间复杂度O(mlogn)
发表于 2016-07-01 20:52:20 回复(0)
我感觉我这样比较容易理解,也比较透彻:
任意选择一个数,从这个数的角度看:上:比它小,下:比它大,左:比它小,右:比它大;
然后注意到二维数组四个角上面的数比较特殊左上跟右下要不都比它大,要不都比它小,★而左下跟右上有两条回路 ">"跟"<" 从左上到到右下相当于一条从小到大的"直线"(另一条  也一样),那么我们得到了这条直线,就可以判断target是否在上面了,如果不在,就得到另一条"直线"(其实是折线)
发表于 2015-11-27 22:26:31 回复(0)
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;
    }
}

由题目可以得知,在左下角的那个数字,上方的都比它小,右边的都比它大,故用目标数字跟左下角的数字进行比较,如果目标数字小,则上移,目标数字大则右移
之前用了二分搜索来解这个题,但是提示我超时了╮( ̄▽ ̄")╭

发表于 2017-06-21 19:56:15 回复(0)
从左下角元素往上查找,右边元素是比这个元素大,上边是的元素比这个元素小。于是,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 回复(0)
每一行都是有序的,那么对每一行进行二分查找,时间复杂度为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;
编辑于 2017-07-17 21:27:17 回复(0)
《剑指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;
}
编辑于 2017-07-09 16:05:35 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋