【剑指Offer题解：java】二维数组中的查找

ゝ一世哀愁。 2023-01-08 06:23 88阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、思路分析
     *   *  一、思路一
         *   *  1、思路分析
             *  2、图解
             *  3、代码实现
         *  二、思路二

## 一、题目 ##

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

## 二、思路分析 ##

### 一、思路一 ###

#### 1、思路分析 ####

> 从左下找

利用该二维数组的性质：

*  每一行都按照从左到右递增的顺序排序，
 *  每一列都按照从上到下递增的顺序排序

改变个说法，即对于左下角的值 m，m 是该行最小的数，是该列最大的数

每次将 m 和目标值 target 比较：

1.  当 m < target，由于 m 已经是该行最大的元素，想要更大只有从列考虑，取值右移一位
2.  当 m > target，由于 m 已经是该列最小的元素，想要更小只有从行考虑，取值上移一位
3.  当 m = target，找到该值，返回 true

用某行最小或某列最大与 target 比较，每次可剔除一整行或一整列

#### 2、图解 ####

查找过程：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70 1]

#### 3、代码实现 ####

public static boolean Find3(int target, int[][] array) { 
            int line = array.length - 1;//行号
            int column = 0;//记录列号
            boolean flag = false;
            while (true) { 
                if (line < 0 || column > array[0].length - 1) break;//超出数组范围 
                if (array[line][column] == target) return true;//表示找到
                if (array[line][column] > target) line--; //目标数小于该数时，直接排除这一行
                else if (array[line][column] < target) column++;//大于该数排除这一列
            }
            return false;
        }

### 二、思路二 ###

> 暴力解题，逐个寻找，找到返回true

代码：

public static boolean Find(int target, int[][] array) { 
            boolean flag = false;
            for (int i = 0; i < array.length; i++) { 
                for (int j = 0; j < array[i].length; j++) { 
                    if (target == array[i][j]) { 
                        flag = true;
                        break;
                    }
                }
                if (flag) break;
            }
            return flag;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70]: /images/20221119/8e2633e5be574750ab54aa0d725e451d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210119122643197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODk1Mzk3,size_16,color_FFFFFF,t_70