題目連結:
題目意譯:
給定一個按升序排列的整數陣列 nums ,找到一個目標值 target 於其中的開始位置以及結束位置。
如果 target 不存在於陣列中,回傳 [-1, -1]。
進階: 你可以寫出一個演算法其執行期間時間複雜度為 O(log n)?
限制:
0 ≦ nums.length ≦ 10 ^ 5
-10 ^ 9 ≦ nums[i] ≦ 10 ^ 9
nums 為非遞減陣列。
-10 ^ 9 ≦ target ≦ 10 ^ 9
範例測資:
範例 1:
輸入: nums = [5,7,7,8,8,10], target = 8
輸出: [3,4]
範例 2:
輸入: nums = [5,7,7,8,8,10], target = 6
輸出: [-1,-1]
範例 3:
輸入: nums = [], target = 0
輸出: [-1,-1]
解題思維:
利用二分搜尋法(Binary Search,見
這題)將第一個不小於(即大於等於) target 以及第一個大於 target 的這兩個位置 i 、 j 都找出來。
如果 target 不存在於陣列中(可以根據上面的結果得知),則回傳 [-1, -1];反之,則 [i, j - 1] 即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。