題目描述

在⼀個⼆維數組中（每個⼀維數組的⻓度相同），每⼀⾏都按照從左到右遞增的順序排序，每⼀列都按照從上到下遞增的順序排序。請完成⼀個函數，輸⼊這樣的⼀個⼆維數組和⼀個整數，判斷數組中是否含有該整數。

例⼦，輸⼊⼀個數組：

num[3][4] = [
1 , 4 , 6 , 28 ,
2 , 7 , 32 , 30 ,
10 , 11 , 67 , 79
]

需要查找⼀個數字 32 ，則返回 true 。

思路及解答

暴⼒破解

直接暴⼒遍歷，最簡單，但顯然，在最壞的情況下需要遍歷完所有的元素才能獲取結果。

如果這個數組規模是 n * m ，那麼時間複雜度就是 O(n × m) ，沒有藉助其他的空間，空間複雜度為 O(1) 。

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 檢查輸入是否為空或無效
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 暴力破解：遍歷整個二維數組
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == target) {
                    return true;
                }
            }
        }

        // 如果遍歷完所有元素都沒有找到目標值，返回false
        return false;
    }
}

• 時間複雜度：O(n × m)

• 空間複雜度： O(1)

  ⽐較查找法

題目提示了，每⼀⾏都按照從左到右遞增的順序排序，每⼀列都按照從上到下遞增的順序排序，那我們其實就可以利用矩陣的排序特性可以從右上角或左下角開始查找，從而優化搜索效率。

具體來説：從右上角開始：

- 如果當前元素等於目標值，返回 `true`。
- 如果當前元素大於目標值，向左移動一列。
- 如果當前元素小於目標值，向下移動一行。

而如果是從左上角開始找，這種兩個方向都更大， 如果從右下角開始找，兩個方向都更小，顯然無法完成搜索。

public class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 檢查輸入是否為空或無效
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;

        // 從右上角開始查找
        int row = 0;
        int col = cols - 1;

        while (row < rows && col >= 0) {
            if (matrix[row][col] == target) {
                return true;
            } else if (matrix[row][col] > target) {
                col--; // 向左移動一列
            } else {
                row++; // 向下移動一行
            }
        }

        // 如果遍歷完所有可能的位置都沒有找到目標值，返回false
        return false;
    }
}

• 時間複雜度： O(m + n)，其中 m 是行數，n 是列數。
• 空間複雜度：O(1)