Re: [閒聊] 每日leetcode已回收
幹你老師，打到一半閃退是三小
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
→
05/17 22:09,
1年前
, 1F
05/17 22:09, 1F
→
05/17 22:09,
1年前
, 2F
05/17 22:09, 2F
推
05/17 22:10,
1年前
, 3F
05/17 22:10, 3F
推
05/17 22:11,
1年前
, 4F
05/17 22:11, 4F
→
05/17 22:13,
1年前
, 5F
05/17 22:13, 5F
→
05/17 22:14,
1年前
, 6F
05/17 22:14, 6F
討論串 (同標題文章)
完整討論串 (本文為第 236 之 1554 篇)：