Given an array of integers nums
sorted in non-decreasing order, find the starting and ending position of a given target
value.
If target
is not found in the array, return [-1, -1]
.
You must write an algorithm with O(log n)
runtime complexity.
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 Output: [-1,-1]
Constraints:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums
is a non-decreasing array.-109 <= target <= 109
SOL:
以為自己已經懂了 binary search ,結果遇到 Medium 還是有卡住。
這題用暴力法的話,for迴圈一次 O(n) 就可以解決了,但因為題目要求 O(log n) ,所以必須用兩次 binary search,分別找starting 跟 ending position,時間複雜度會是 O(2*log n),不過2是常數,所以有符合題目要求的 O(log n)。
不過因為執行時間只有打敗9%的人,所以我參考別人的程式,來改進一下我的。
這個作者使用更精簡的寫法,把 binary search 定義成一個 function,用 leftBias 這個 flag 來決定是找starting 還是 ending position。
另外,我發現自己還是不太熟悉 self 這個用法。
一開始直接寫 startPos = binSearch(self, nums, target, True),程式直接報錯。
最後附上兩個 Submit 的結果:
Reference:
1. LeetCode-34. Find First and Last Position of Element in Sorted Array
2. First and Last Position of Element in Sorted Array - Binary Search - Leetcode 34
留言列表