主題

LeetCode - 34. Find First and Last Position of Element in Sorted Array 解題心得

Not In My Back Yard | 2021-05-07 00:00:04 | 巴幣 0 | 人氣 28

題目連結:


題目意譯:
給定一個按升序排列的整數陣列 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] 即為所求。




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

創作回應

更多創作