乐趣区

剑指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;
    }
}
退出移动版