【LeetCode】劍指 Offer 04. 二維數組中的查找 p44 -- Java Version

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

1. 題目介紹（04. 二維數組中的查找）

在一個 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

2. 題解

2.1 暴力枚舉 – O(nm)

時間複雜度O(nm)，空間複雜度O(1)

class Solution {
    // 暴力枚舉
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 1. 判斷數組是否為空，如果是則傳回false
        if (matrix.length <= 0) return false;
        // 2. 定義變量，記錄二維數組的行列
        int n = matrix.length;
        int m = matrix[0].length;
        // 3. 循環周遊每一個值，直到找到正确結果
        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (matrix[i][j] == target) return true;
            }
        }
        // 4. 循環結束，數組中不存在target
        return false;
    }
}
           

2.2 “标記數”數組剔除 – O(n+m)

時間複雜度O(n+m)，空間複雜度O(1)

class Solution {
    // 标記數數組剔除
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 1. 判斷數組是否為空，如果是則傳回false
        if (matrix.length <= 0) return false;
        // 2. 定義變量，記錄二維數組的行列
        int row = 0, col = matrix[0].length-1;
        // 
        while (col >= 0 && row < matrix.length){
            if (matrix[row][col] > target) col--;
            else if (matrix[row][col] < target) row++;
            else return true;
        }
       
        // 4. 循環結束，數組中不存在target
        return false;
    }
}
           

3. 思考

沒想到，用窮舉在力扣的測試用例裡面也這麼快，感覺還是限制條件太小了。

4. 參考資料

[1] 面試題04. 二維數組中的查找（标志數，清晰圖解）