转载

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

一、题目

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

二、思路分析

该二维数组的特点：

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

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

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

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

变量名的含义：

array：二维数组。

target：要寻找的目标值。

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

思路分析：

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

思路分析：

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

原文 https://segmentfault.com/a/1190000020452559

正文到此结束