二维数组中的查找—在一个递增的二维数组中判断给定数是否在数组当中

163 阅读 0 评论 108 点赞

我是靠谱客的博主矮小火，这篇文章主要介绍二维数组中的查找—在一个递增的二维数组中判断给定数是否在数组当中，现在分享给大家，希望可以做个参考。

题目描述

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

解题思路：

1、首先这是一个二维数组，并且按行按列递增，如下：

复制代码

1
2
3
4
5
1    2    3    4    5
6    7    8    9    10
11   12   13   14   15
16   17   18   19   20

2、按照正常思维考虑，你会想到遍历整个二维数组，存在返回true 不存在返回false。但是这样太浪费时间
3、我们需要利用二维数组的递增顺序来更快速查找
4、从第一行的最大下标处开始判断，如果给定数字大于数组下标数字，指针向下遍历；如果小于则向左遍历，找到返回true、没找到返回false。

代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public boolean Find(int target, int [][] array) {
        int i = 0;
        int j = array.length-1;
        while((i < array[0].length) && (j >= 0)){
            if(target < array[i][j]){
                j--;
            }else if(target > array[i][j]){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }
}