剑指offer二维数组的查找Java-版

一、题目

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

二、思路分析

该二维数组的特点：

二维数组 右上角的数 是该行最大值，该列最小值。

二维数组 左下角的数 是该行最小值，该列最大值。

所以我们可以从这两个方向入手。

1、从二维数组右上角的数入手

变量名的含义：

array：二维数组。

target：要寻找的目标值。

array [i] [j] 为二维数组中要和 target 比较的数，初始值为二维数组右上角的值。

思路分析：

1. 二维数组数组合法性判断。
2. 循环开始。（二维数组越界，循环停止）
3. 当 target > array [i] [j]，由于该行的其他数都比当前数大，说明要找的数不在这行，行下移。
4. 当 target < array [i] [j]，由于该列的其他数都比当前数小，说明要找的数不在这列，列左移。
5. 当 target == array [i] [j]，返回 true。
6. 如果循环结束后还是没有返回值，说明当前二维数组没有满足我们要求的数，返回 false。

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

2、从二维数组左下角的数入手

变量名的含义：

array：二维数组。

target：要寻找的目标值。

array [i] [j] 为二维数组中要和 target 比较的数，初始值为二维数组左下角的值。

思路分析：

1. 二维数组数组合法性判断。
2. 循环开始。（二维数组越界，循环停止）
3. 当 target > array [i] [j]，由于该列的其他数都比当前数小，说明要找的数不在这列，列上移。
4. 当 target < array [i] [j]，由于该行的其他数都比当前数大，说明要找的数不在这行，行右移。
5. 当 target == array [i] [j]，返回 true。
6. 如果循环结束后还是没有返回值，说明当前二维数组没有满足我们要求的数，返回 false。

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