難度: Medium
類型: Array, Binary Search
CPP程式下載: 33.cpp
前情題要:
在一個旋轉移動過原本小到大排序的陣列中, 尋找一個target數字。
思考方式:
這題也是, 想到方法就簡單, 沒想到方法就會超時。方法不好想, 但是容易看得懂。
1. 原本的陣列是小到大排序過的, 所以每個數字的右邊都是比較大的數或是0。
2. 用 binary search 比較快, 如果陣列的中間那個值比最左邊的值大, 代表他在上升序列中, 最大值和0都在他的右邊。這時候如果 target 值在中間那個和最左邊值的中間, 那就看左邊的序列就好。反之就看右邊的序列。
3. 如果中間的那個值比左邊小, 代表最大值和0都在中間那個數字的左邊。如果target小於最右邊的值, 但大於中間那個數字, 則代表target值要位於中間偏右, 反之則在左半側。
4. 一直縮小一半, 直到找到 target 的值或是已經夾擊找到最後一個值都不等於 target。
複雜度思考:
Time Complexity: O( log2(N) )
Space Complexity: O( x )
結果:
Runtime: 0 ms, Beats: 100%
Memory: 10.10 MB, Beats: 66.35%
