二維數組中的查找如何實現？看圖！

點擊關注上方“ 圖解面試算法 ”，

設爲“置頂或星標”，一起刷 LeetCode。

作者：程序員吳師兄

今天分享的題目來源於 LeetCode 上的劍指 Offer 系列 04 . 二維數組中的查找 。

題目鏈接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

一、題目描述

在一個 n * m 的二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

示例:

現有矩陣 matrix 如下：

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

給定 target = 5，返回 true。

給定 target = 20，返回 false。

限制：

0 <= n <= 1000
0 <= m <= 1000

二、題目解析

仔細觀察矩陣，可以發現： 左下角元素 爲所在列最大元素，所在行最小元素

如果 左下角元素 大於了目標值，則目標值一定在該行的上方，左下角元素所在行可以消去。

如果 左下角元素 小於了目標值，則目標值一定在該列的右方，左下角元素所在列可以消去。

具體操作爲從矩陣左下角元素開始遍歷，並與目標值對比：

```
matrix[i][j] > target
i--
i
```
```
matrix[i][j] < target
j++
j
```
當 matrix[i][j] == target 時：返回 true。
如果越界，則返回 false。

三、動畫描述

四、圖片描述

五、參考代碼

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //初始化 i 和 j 爲數組左下角元素
        int i = matrix.length - 1, 
        int j = 0;
        //如果 i 和 j 沒有越界繼續判斷
        while(i >= 0 && j < matrix[0].length){
            
            if(matrix[i][j] > target){
                //行索引向上移動一格（即 i-- ），即消去矩陣第 i 行元素
                i--;
            }else if(matrix[i][j] < target){
                //列索引向右移動一格（即 j++ ），即消去矩陣第 j 列元素
                j++;
            }else{
                //找到目標值，直接返回 ture
                return true;
            }     
        }
        //沒有找到目標值，返回 false
        return false;
    }
}