ETH官方钱包

前往
大廳
主題

LeetCode - 1901. Find a Peak Element II 解題心得

Not In My Back Yard | 2023-02-28 12:00:01 | 巴幣 0 | 人氣 214

題目連結:


題目意譯:
一個二維陣列中一個尖峰元素為一元素其嚴格大於其鄰近元素,也就是其上下左右相鄰的鄰居。

給定一個索引值從 0 開始的矩陣 mat,其中沒有兩個相鄰格子是一樣的,請找到任一一個尖峰元素 mat[i][j] 並以長度 2 的陣列 [i,j] 之形式回傳。

你可以假設整個矩陣是被一整圈 -1 之值包在外側。

你必須撰寫一個演算法其時間複雜度為 O(m log(n)) 或是 O(n log(m))。

限制:
m == mat.length
n == mat[i].length
1 ≦ m, n ≦ 500
1 ≦ mat[i][j] ≦ 10 ^ 5
沒有兩個相鄰格子是一樣的。



範例測資:
範例 1:
輸入: mat = [[1,4],[3,2]]
輸出: [0,1]
解釋: 3 和 4 都是尖峰元素,所以 [1,0] 和 [0,1] 都是可被接受的答案。

範例 2:
輸入: mat = [[10,20,15],[21,30,14],[7,16,32]]
輸出: [1,1]
解釋: 30 和 32 都是尖峰元素,所以 [1,1] 和 [2,2] 都是可被接受的答案。


解題思維:
其實就是系列第一題的推廣而已。而因為現在有「第二個」方向要考慮(假設我們是對「行」做二分搜),因此我們需要先掃過一次另一個方向(承前,這邊則為「列」),看哪個元素是該方向中最大者。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

LULU
看了這麼多解釋還是看不出用 binary search 的必要性是什麼, 就算用 2 層 for 迴圈執行速度也沒有區別
binary search 到底要怎麼為這題加速....
2023-11-25 22:33:01
Not In My Back Yard
最簡單的解釋:題目要求。
我想這個條件應該就夠說服你了。
2023-11-25 23:58:59
Not In My Back Yard
如果你是想問為何二分搜尋法會「可以使用」在這題上,那麼你就要先回到其系列第一題
http://www.jamesdambrosio.com/artwork.php?sn=5320668
上連同本題一起去想——為何兩題的條件都包含了「相鄰元素保證不同」以及「陣列的邊界『外面』被足夠小的數字包住」。



(以下先以系列第一題為例)
因為這兩個條件可以推得陣列中有「至少」一座「山」(也就是廣義版的「尖峰元素」,其大過的不只是左右鄰居以及鄰居的鄰居、鄰居的鄰居的鄰居、……直到不能再往左右延伸為止)。

而不論我們現在位於陣列的何處,只要我們看到「上坡」就往「高處」爬。而線性搜尋的話就會找到現在位於的這座「山」之頂端;而二分搜尋法的話,有機會會在各個山之間跳來跳去,但是由於搜尋範圍會越來越小再加上我們都是往「山上」跑,因此最後必定會落在某個「山」的「頂端」。

而這就是為了系列第一題會可以使用二分搜來解。



至於第二題也是類似的思路,不過因為多了另一個方向再加上二分搜有可能會在各個山之間跳來跳去,因此最後兩個方向最後找到的極有可能不是同一個位置。正因如此,某一個方向才只能只用線性搜尋。

以上。
2023-11-26 00:32:13

更多創作