[劍指-Offer] 4. 二維數組中的查找(數學、二分法)

文章目錄

• • 1. 題目來源
  • 2. 題目說明
  • 3. 題目解析
  • • 3.1 方法一：暴搜
    • 3.2 方法二：數學規律法

1. 題目來源

連結：二維數組中的查找

來源：LeetCode——《劍指-Offer》專項

2. 題目說明

在一個

n * m

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

示例 ：

[

[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

3. 題目解析

3.1 方法一：暴搜

這是個沒有營養的解答，會浪費你 10 秒鐘~~~

// 執行用時 :28 ms, 在所有 C++ 送出中擊敗了96.72%的使用者
// 記憶體消耗 :12.2 MB, 在所有 C++ 送出中擊敗了100.00%的使用者
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) 
            return false;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[0].size(); ++j) {
                if (matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }
};
           

3.2 方法二：數學規律法

仔細觀察題目中給的那個例子，如果從左上角開始搜尋，它的右方與下方都是增長方向，從右下角開始搜尋，它的上方與左方都是增長方向，無法進行判斷。故搜尋不能從這兩個标志數開始，需要找到一方增長、一方減小的路徑，滿足

if

else

結構才能夠完成。

可以發現有兩個位置的數字很有特點，左下角和右上角的數。左下角的18，往上所有的數變小，往右所有數增加，那麼就可以和目标數相比較：

• 如果目标數大，就往右搜
• 如果目标數小，就往上搜

這樣就可以判斷目标數是否存在。當然也可以把起始數放在右上角，往左和下搜，停止條件設定正确就行。

如果數組為空、目标數小于

matrix[0][0]

大于

matrix.back().back()

直接傳回

false

即可。時間複雜度： O ( m + n ) O(m + n) O(m+n)

參見代碼如下：

// 執行用時 :52 ms, 在所有 C++ 送出中擊敗了18.44%的使用者
// 記憶體消耗 :12.2 MB, 在所有 C++ 送出中擊敗了100.00%的使用者

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) 
            return false;
        if (target < matrix[0][0] || target > matrix.back().back()) 
            return false;
        int x = matrix.size() - 1, y = 0;
        while (true) {
            if (matrix[x][y] > target) 
                --x;
            else if (matrix[x][y] < target) 
                ++y;
            else 
                return true;
            if (x < 0 || y >= matrix[0].size()) 
                break;
        }
        return false;
    }
};