[[376062]]

二維數組中的查找

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

解法一

題目理解起來很簡單，一個二維數組，一個數字。判斷數組里面有沒有這個數字。

另外還有一個提干是每一行每一列都是數字遞增，待會再看看這個題干怎么利用起來。

如果只是一個數組里面找數字，那么很容易想到的就是直接遍歷。

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, columns = matrix[0].length; 
        for (int i = 0; i < rows; i++) { 
            for (int j = 0; j < columns; j++) { 
                if (matrix[i][j] == target) { 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
} 

方法消耗情況

執行用時：0-1 ms 
內存消耗：44.3 MB 

時間復雜度

由于用到了二維數組的遍歷，所以時間復雜度就是O(mn)，用到了時間復雜度的乘法計算。

空間復雜度

除了本身的數組，只用到了幾個變量，所以空間復雜度是O(1)。

解法二

接下來我們就看看怎么利用剛才說到的數字遞增題干，得出新的更簡便的解法呢?

由于每一行的數字都是按循序排列的，所以我們很容易就想到用二分法來解決，也就是遍歷每一行，然后在每一行里面進行二分法查詢。

class Solution { 
     public boolean findNumberIn2DArray(int[][] matrix, int target) { 
        for (int i = 0; i < matrix.length; i++) { 
            int left = 0; 
            int right = matrix[0].length-1; 
            while (left<=right) { 
                int middle = (left + right) / 2; 
                if (target == matrix[i][middle]) { 
                    return true; 
                } 
                if (target > matrix[i][middle]) { 
                    left = middle + 1; 
                } else { 
                    right = middle - 1; 
                } 
            } 
        } 
        return false; 
    } 
} 

方法消耗情況

執行用時：0-1 ms 
內存消耗：44.4 MB 

時間復雜度

二分法的復雜度大家應該都知道吧，O(logn)。具體算法就是 N *(1/2)^x=1,得出來x=logn，底數為2。

所以在外面套一個循環，總的時間復雜度就為O(mlogn)，底數為2

空間復雜度

由于也沒有用到額外的跟n有關的空間，所以空間復雜度是O(1)。

解法三

但是，剛才的解法還是沒有完全用到題目的特性，這個二維數組不僅是每行進行了排序，每列也進行了排序。

所以，該怎么解呢?

我們可以把這個數組轉個角度看看，轉45度角：

[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]

        15 
      11  19 
    7   12   22  
  4    8   16    24 
1   5    9    17    30 
 
... 

下面就不寫了，是不是像一個二叉樹的結構了?而且每個節點的左分支是一定小于這個元素的，右分支是一定大于這個元素的。

那么根據這個特點，我們又可以寫出一種更簡便的算法了，也就是從第一行的最后一個數字開始，依次和目標值比較，如果目標值大于這個節點數，就把節點往下移動，也就是行數+1。如果目標值小于這個節點數，就把節點向左移動，也就是列數-1。

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

方法消耗情況

執行用時：0-1 ms 
內存消耗：44.5 MB 

時間復雜度

代碼量確實少了很多，那么時間復雜度有沒有減少呢?

可以看到，只有一個while循環，從右上角開始找，如果最壞情況就是找到左下角，也就是移動到最下面一行的第一列，那么時間復雜度就是O(m+n)了。

一個是mlogn(底數為2)，一個是m+n，也不能斷定哪個小,但是m和n比較大的時候肯定是加法得出的結果比較小的，所以這種解法應該是最優解法了。

空間復雜度

同樣，空間角度，沒有使用額外的和n相關的空間，所以空間復雜度為O(1)

參考

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

本文轉載自微信公眾號「碼上積木」，可以通過以下二維碼關注。轉載本文請聯系碼上積木公眾號。