【牛客 - 剑指offer】JZ4 二维数组中的查找 Java实现

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

知识分类篇 - 搜索算法 - JZ4 二维数组中的查找

题目

题目主要信息

• 矩形的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复

• 找到矩阵中有没有给定的元素即可

方案一 朴素思想

从下向上、从左到右遍历二维数组的每一层

• 如果数组中的元素值，等于target，返回true

• 如果不等于，且当前数已经比target大了，则结束这一层的遍历，去到上一层进行遍历

public class Solution {
    public boolean Find(int target, int[][] array) {

        for (int i = array.length - 1; i >= 0; i--) {

            for (int j = 0; j < array[i].length; j++) {
                if (array[i][j] == target) {
                    return true;
                }
                if (array[i][j] > target) {
                    break;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

方案二 分治

分治即“分而治之”

• “分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题，子问题继续按照这样划分，直到问题可以被轻易解决

• “治”指的是将子问题单独进行处理

经过分治后的子问题，需要将解进行合并才能得到原问题的解，因此整个分治过程经常用递归来实现

找规律：

• 左上角元素是最小值

• 右下角元素是最大值

• 左下元素大于它上方的元素，小于它右方的元素

• 右上元素小于它下方的元素，大于它左方的元素

既然左下角元素有这么一种规律，相当于将要查找的部分分成了一个大区间和一个小区间，每次与左下角元素比较，就知道目标应该在哪部分中，于是利用分治思想来做。

具体做法

1. 首先获取矩阵的两个边长，判断特殊情况

2. 首先以左下角为起点，若它小于目标元素，就往右去找大的，若是它大于目标元素，则往上移动去找小的

3. 若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19