Leetcode — 240. Search a 2D Matrix II (中文)

問題連結: https://leetcode.com/problems/search-a-2d-matrix-ii/

寫一個演算法讓我們可以有效率地知道我們能否在 m*n 的矩陣matrix 中找到target 且matrix 有下列特性

• 每列的所有數字從左到右都是由小到大排列
• 每行的所有數字從上到下都是由小到大排列

範例
Input: 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
Output: true

想法:

解這題的方法跟我們在解 74. Search a 2D Matrix 完全不同, 因為在第74題中, 我們矩陣的條件是只有每列都有排序,每行並沒有排序; 並且矩陣還有一個特點- 每列的最後一個數字絕對小於等於下一列的第一個數字, 而因為這些特性, 讓我們其實可以把第74題的二維陣列輕鬆併為已排序好的一維陣列, 我們只要把一列一列併在一起, 幫他們給個新的"位置號碼", 他們就已排序好了, 因此我們也可以用二元搜索法(binary search)來搜尋我們的目標數字在不在這個陣列中, 只需花O(lg(m*n))的時間就可以解完第74題

以下為第74題中 0ms 的程式碼:

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        if(matrix[0][0]>target || matrix[m-1][n-1]<target)
            return false;
        //if consider a 1D array, each num (matrix[i][j]) will be considered at: matrix[n*i+j]
        int s = 0, e = n*m-1;
        while(s<=e)
        {
            int mid = s + (e-s)/2; 
            int i = mid/n; 
            int j = mid%n;
            if(matrix[i][j]==target)
                return true;
            if(matrix[i][j]<target)
                s = mid+1;
            else 
                e = mid-1;
        }
        return false;
    }

而這題的矩陣條件不同, 矩陣中不但在各列也在各直行按數字大小排序
因此我們不能直接像第74題一樣,把所有列都併在一起後還能得到維持排序的一維陣列, 因此我們必須多花O((m*n)lg(m*n))時間排序整個一維陣列,才能用二元搜索來找目標數字

因此, 我們必須好好利用矩陣各列跟各直行都排序好的特點, 從這句話我們也可以解釋成現在位置數字matrix[i][j]一定小於他的右格matrix[i][j+1]和他下格matrix[i+1][j]

我的第一個想法就是我們從左上角(0,0)開始走訪整個矩陣
若目標數字比現在的數字還要小的話, 我們直接回傳false, 因為我們就算往右或往下走都無法找到比現在數字還小的數字
若目標數字比現在數字還要大的話, 我們往右走跟往下走都有可能找到目標數字, 而因為我們不知道目標數字到底會在哪, 因此兩種方向我們都必須嘗試, 因此我們會一直在條件符合後一再的兵分兩路, 直到我們已走到底都沒找到, 或者直到我們在某條路線中已找到目標數字

因此以下程式碼在Leetcode上只過了124/128個test cases, 最後敗在時間複雜度過高而超過時間:

public boolean searchMatrix(int[][] matrix, int target) {
        return helper(matrix,0,0,target);
    }
    public boolean helper(int[][] arr,int i,int j, int target){
        if(i>=arr.length||j>=arr[i].length||arr[i][j]>target)
            return false;
        if(arr[i][j]==target)
            return true;
        return helper(arr,i+1,j,target)||helper(arr,i,j+1,target);
    }

上述程式碼中, 我們只有在目標數字比現在數字還要小的時候, 我們可以果斷停止繼續往下走, 其他時候我們都不斷的兵分兩路, 而這造成我們很有可能不斷的兵分兩路到重複的格子, 比如說我們可能會走訪位置(1,1)兩次, 因為他們的前一格就是(0,1)跟(1,0), 都可能因為條件符合而走到同一格, 而一個格子可能會被造訪一次以上甚至以2的倍數成長
有沒有方法讓我們可以保證走訪同個格子至多一次而已?

程式邏輯:

我們需要找到一個方法讓我們可以在現在位置數字是matrix[i][j]的時候, 希望條件達成的時候(例如 想找大數字 或想找小一點的數字)可以一次只需要走一個方向, 而不是像從左上角開始, 雖然想找小數字時就會停下, 但只要想找大數字就需要左側跟右側都試跑一遍

若我們從右下角開始往回走訪, 那結果也是一樣, 我們每次在想要找更小的數字的時候都需要往上和往左走
但是如果我們是從左下或右上角走的話, 我們若想要找更小或更大的數字的時候, 我們只需要往一個方向走就好

而假設我選從矩陣的左下角開始, 那我們來看看為何這樣改起始點就可以減少時間複雜度👉

你可能會覺得為何從左下角matrix[n-1][0]開始這麼特別?

因為現在我們已在最下面的一列了, 代表在這格之下也不會有比他大的數字; 也因為我們已在最左格, 代表在這格的左邊也不會有比他小的數字
而由上述兩個事實可得知, 若我們現在想要找比現在位置數字還要大的數字, 我們只能往右找; 若我們想要找比現在位置數字還要小的數字, 我們只能往上找, 我們每次都只會有一個方向需要走, 而不需要一次跑兩個方向 增加時間複雜度 (從右上角開始也是相同邏輯, 但相反方向)

而這樣的邏輯只需要O(m+n)的時間複雜度, 因為我們在迴圈中每次都會依條件來判斷是要往右走一格還是往上走一格

以下為5ms的程式碼, 贏過47% —

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        return helper(matrix,m-1,0,target);
    }
    public boolean helper(int[][] arr,int i,int j, int target){
        if(i<0||j<0||i>=arr.length||j>=arr[i].length)
            return false;
        if(arr[i][j]==target)
            return true;
        if(arr[i][j]<target)
            return helper(arr,i,j+1,target);
        else
            return helper(arr,i-1,j,target);
    }

或者不要用遞迴的方式, 可以得到4ms的程式碼, 贏過99% —

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

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