→ oinishere: 內推我 05/17 22:09
→ DJYOSHITAKA: 別捲了 05/17 22:09
推 OnishiSaori: 別捲了 05/17 22:10
推 wu10200512: 別捲了 05/17 22:11
→ sustainer123: 別卷了 05/17 22:13
→ argorok: 別卷了 05/17 22:14
幹你老師，打到一半閃退是三小
34. Find First and Last Position of Element in Sorted Array
有一個遞增的array nums
並且給一個target，請找出該array中target出現的第一個和最後一個index
如果target沒有出現在nums中回傳[-1,-1]
思路:
標準的二分搜尋法
在二分搜尋法中，會這樣寫
if nums[mid]<target{
left=mid+1
}else{
right=m
}
這樣會找到第一個出現的target
接著將二分搜尋法改寫成
if nums[mid]>target{
right=mid
}else{
left=mid+1
}
這樣可以找到最後一個target後一位的數字
這樣就可以回傳答案了
golang code:
func searchRange(nums []int, target int) []int {
n := len(nums)
if n == 0 {
return []int{-1, -1}
}
l, r := 0, n-1
res := []int{-1, -1}
for r > l {
m := l + (r-l)/2
if nums[m] < target {
l = m + 1
} else {
r = m
}
}
if nums[l] != target {
return []int{-1, -1}
}
res[0] = l
nums = append(nums, 1000000001)
r = n
for r > l {
m := l + (r-l)/2
if nums[m] > target {
r = m
} else {
l = m + 1
}
}
res[1] = l - 1
return res
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.211 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715954896.A.559.html