剑指offer——二维数组中的查找

题目描述

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

案例数组:

Approach 1：暴力解决法

所占时间，内存：215ms，18000k

思路：逐行逐列去遍历

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

Approach 2：根据规律查询

所占时间，内存：207ms，16112k

思路：

* 矩阵是有序的，从左下角来看，向上数字递减，向右数字递增，

* 因此从左下角开始查找，当要查找数字比左下角数字大时。右移

* 要查找数字比左下角数字小时，上移

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

Tips:

1、数组的声明和初始化

//一维数组
int[] a = new int[4];
int[] b = {1,2,3,4};

//二维数组
int[][] c = new int[4][4];
int[][] d = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};

2、获得二维数组列的最大长度，行的最大长度

int[][] x = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
int row = x.length;
int col = x[0].length;