LeetCode 74,直擊BAT經典面試題_網頁設計公司

網頁設計公司推薦不同的風格,搶佔消費者視覺第一線

透過選單樣式的調整、圖片的縮放比例、文字的放大及段落的排版對應來給使用者最佳的瀏覽體驗,所以不用擔心有手機版網站兩個後台的問題,而視覺效果也是透過我們前端設計師優秀的空間比例設計,不會因為畫面變大變小而影響到整體視覺的美感。

本文始發於個人公眾號:TechFlow,原創不易,求個關注

今天是LeetCode專題43篇文章,我們今天來看一下LeetCode當中的74題,搜索二維矩陣,search 2D Matrix。

這題的官方難度是Medium,通過率是36%,和之前的題目不同,這題的點贊比非常高,1604個贊,154個反對。可見這題的質量還是很高的,事實上也的確如此,這題非常有意思。

題意

這題的題意也很簡單,給定一個二維的數組matrix和一個整數target,這個數組當中的每一行和每一列都是遞增的,並且還滿足每一行的第一個元素大於上一行的最後一個元素。要求我們返回一個bool變量,代表這個target是否在數組當中。

也就是說這個是一個典型的判斷元素存在的問題,我們下面來看看兩個樣例:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

題解

這題剛拿到手可能會有些蒙,我們當然很容易可以看出來這是一個二分的問題,但是我們之前做的二分都是在一個一維的數組上,現在的數據是二維的,我們怎麼二分呢?

我們仔細閱讀一下題意,再觀察一下樣例,很容易發現,如果一個二維數組滿足每一行和每一列都有序,並且保證每一行的第一個元素大於上一行的最後一個元素,那麼如果我們把這個二維數組reshape到一維,它依然是有序的。

比如說有這樣一個二維數組:

[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]

它reshape成一維之後會變成這樣:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

reshape是numpy當中的說法,也可以簡單理解成把每一行串在一起。所以這題最簡單的做法就是把矩陣降維,變成一位的數組之後再通過二分法來判斷元素是否存在。如果偷懶的話可以用numpy來reshape,如果不會numpy的話,可以看下我之前關於numpy的教程,也可以自己用循環來處理。

reshape之後就是簡單的二分了,完全沒有任何難度:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        import numpy as np
        arr = np.array(matrix)
        # 通過numpy可以直接reshape
        arr = arr.reshape((-1, ))
        l, r = 0, arr.shape[0]
        if r == 0:
            return False
        # 套用二分
        while l+1 < r:
            m = (l + r) >> 1
            if arr[m] <= target:
                l = m
            else:
                r = m
        return arr[l] == target

正經做法

引入numpy reshape只是給大家提供一個解決的思路,這顯然不是一個很好的做法。那正確的方法應該是怎樣的呢?

還是需要我們對問題進行深入分析,正向思考感覺好像沒什麼頭緒,我們可以反向思考。這也是解題常用的套路,假設我們已經知道了target這個数字存在矩陣當中,並且它的行號是i,列號是j。那麼根據題目當中的條件,我們能夠得出什麼結論呢?

我們分析一下元素的大小關係,可以得出行號小於i的所有元素都小於它,行號大於i的所有元素都大於它。同行的元素列號小於j的元素小於它,列號大於j的元素大於它。

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

節能減碳愛地球是景泰電動車的理念,是創立景泰電動車行的初衷,滿意態度更是服務客戶的最高品質,我們的成長來自於你的推薦。

也就是說,行號i就是一條隱形的分界線,將matrix分成了兩個部分,i上面的小於target,i下方的大於target。所以我們能不能通過二分找到這個i呢?

想到這裏就很簡單了,我們可以通過每行的最後一個元素來找到i。對於一個二維數組而言,每行的最後一個元素連起來就是一個一維的數組,就可以很簡單地進行二分了。

找到了行號i之後,我們再如法炮製,在i行當中進行二分來查找j的位置。找到了之後,再判斷matrix[i][j]是否等於target,如果相等,那麼說明元素在矩陣當中。

整個的思路應該很好理解,但是實現的時候有一個小小的問題,就是我們查找行的時候,找的是大於等於target的第一行的位置。也就是說我們查找的是右端點,那麼二分的時候維護的是一個左開右閉的區間。在邊界的處理上和平常使用的左閉右開的寫法相反,注意了這點,就可以很順利地實現算法了:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if n == 0:
            return False
        
        m = len(matrix[0])
        if m == 0:
            return False
        
        # 初始化,左開右閉,所以設置成-1, n-1
        l, r = -1, n-1
        
        while l+1 < r:
            mid = (l + r) >> 1
            # 小於target的時候移動左邊界
            if matrix[mid][m-1] < target:
                l = mid
            else:
                r = mid
                
        row = r
        
        # 正常的左閉右開的二分
        l, r = 0, m
        
        while l+1 < r:
            mid = (l + r) >> 1
            if matrix[row][mid] <= target:
                l = mid
            else:
                r = mid
                
        return matrix[row][l] == target

我們用了兩次二分,查找到了結果,每一次二分都是一個O(logN)的算法,所以整體也是log級的算法。

優化

上面的算法沒有問題,但是我們進行了兩次二分,感覺有些麻煩,能不能減少一次,只使用一次二分呢?

如果想要只使用一次二分就找到答案,也就是說我們能找到某個方法來切分整個數組,並且切分出來的數組也存在大小關係。這個條件是使用二分的基礎,必須要滿足。

我們很容易在數組當中找到這樣的切分屬性,就是元素的位置。在矩陣元素的問題當中,我們經常用到的一種方法就是對矩陣當中的元素進行編號。比如說一個點處於i行j列,那麼它的編號就是i * m + j,這裏的m是每行的元素個數。這個編號其實就是將二維數組壓縮到一維之後元素的下標。

我們可以直接對這個編號進行二分,編號的取值範圍是確定的,是[0, mn)。我們有了編號之後,可以還原出它的行號和列號。而且根據題目中的信息,我們可以確定這個矩陣當中的元素按照編號也存在遞增順序。所以我們可以大膽地使用二分了:

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if n == 0:
            return False
        
        m = len(matrix[0])
        if m == 0:
            return False
        
        l, r = 0, m*n
        
        while l+1 < r:
            mid = (l + r) >> 1
            # 還原行號和列號
            x, y = mid // m, mid % m
            if matrix[x][y] <= target:
                l = mid
            else:
                r = mid
        return matrix[l // m][l % m] == target

這樣一來我們的代碼大大簡化,並且代碼運行的效率也提升了,要比使用兩次二分的方法更快。

總結

這道題到這裏就結束了,這題難度並不大,想出答案來還是不難的。但是如果在面試當中碰到,想要第一時間想到最優解法還是不太容易。這一方面需要我們積累經驗,看到題目大概有一個猜測應該使用什麼類型的算法,另一方面也需要我們對問題有足夠的理解和分析,從而讀到題目當中的隱藏信息

關於這題還有一個變種,就是去掉其中每行的第一個元素大於上一行最後一個元素的限制。那麼矩陣當中元素按照編號順序遞增的性質就不存在了,對於這樣的情況, 我們該怎麼樣運用二分呢?這個問題是LeetCode的240題,感興趣的話可以去試着做一下這題,看看究竟解法有多大的變化。

如果喜歡本文,可以的話,請點個關注,給我一點鼓勵,也方便獲取更多文章。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

南投搬家公司費用,距離,噸數怎麼算?達人教你簡易估價知識!

搬家費用:依消費者運送距離、搬運樓層、有無電梯、步行距離、特殊地形、超重物品等計價因素後,評估每車次單