從LeetCode學演算法 - 56 Binary Search (3)

0240. Search a 2D Matrix II (Medium)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

1
2
3
4
5
6
7
[
  [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]
]

Given target = 5, return true.

Given target = 20, return false.

分析/解題

給定一個m x n的矩陣，此矩陣每列(row)都是從左到右升冪排序；
同時此矩陣每行(column)都是由上到下升冪排序。
試找出一個有效率的演算法，
來處理在這個矩陣搜尋一個值是否在這裡面。

這題乍看之下沒有這麼直觀，如果我們從matrix[0][0]出發的話，
顯然馬上就會碰到問題：
「好現在target比1大，我該往哪邊走？」 看來怎麼走都不對是吧？如果透過暴力的方式來一排一排找，
結果時間複雜度會是O(mn) 。
就算有想到Binary Search 可以處理已排序的陣列，
每次取一行或一列來搜尋值，
時間複雜度也只會降到O(m log n)或O(n log m) ，
似乎還是不那麼理想。

那麼，該怎麼考慮這個題目呢？
翻了翻提示，居然也是寫Binary Search；
而Binary Search的精髓，
其實就在於可以在每次的抉擇中保留需要的那部分的選項 。

那麼，回頭看看上面的矩陣，想要能夠靠選擇每次去掉選項，
我們考慮看看15這個點如何？

當target等於15 的時候，就直接是答案了，回傳true 。
當target不是15 的時候，可以分成比15大，或比15小 。

比15大 的狀況：
代表原先15的一整列(1, 4, 7, 11, 15)已經都不用考慮了 ，
因為15已經是這整列的最大值 ，故我們可以挑到19，
因為19這行還沒看過，
同時(15, 19, 22, 24, 30)這當中也是越來越大，
所以挑選19可以繼續進行比較，
這個操作就相當於扣掉一整列的備選 。
比15小 的狀況：
代表原先15的一整行(15, 19, 22, 24, 30)不用考慮了，
理由跟1.講得相似，只是這次我們就變成往右走挑到11 ，
整個操作相當於扣掉一整行的備選 。

我們每次刪去一行或一列，那麼總共有m列n行的話，
最多就要操作m+n次 才能確認target是否在matrix中。
(因為每次扣掉一行或一列的備選嘛)

所以其實再仔細一看，
如果我們將這個矩陣往逆時針轉45度，
(或將你的頭順時針轉45度)，
你會發現這整個矩陣其實可以當作一個以15為根結點的二元樹 。
(不過由於它的特性，可以想像它還有其它不只二元樹的連結)
(或者更準確的說，它就是有向圖(Oriented Graph) )

所以我們的整個演算法如下：

檢查matrix是否正常，不正常則直接回傳false
將初始點定在**(i, j)=(0, n-1)** 的位置
當i和j都沒有超過邊界 的時候，進行下面的迴圈：
3-a. 若target和當前點的値相等，回傳true
3-b. 否則若target較大，將i遞增
3-c. 否則將j遞減
若迴圈結束尚未回傳，代表這個值不在矩陣內，
回傳false結束。

寫成程式碼如下所附。
(也有人判斷第一步的時候用< 1而非==0，但測試目前沒有明顯差異，
讀者依自己喜好選擇寫法即可。)

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(m+n)/O(1)，因為每次都會刪去一行或一列，最差狀況就是全部刪完。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
Python Taiwan 王彥珽：** 直行橫列**才對(註：中國才是橫行直列XD)
(但我工作就會講row跟column啦)

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

1
2
如果你／妳覺得這篇文章不錯，請給我5個拍手，並且給我5個Like。
(點開最上面的SHOW EMBED!)