first_and_last_in_sorted_array
first_and_last_in_sorted_array.go 源码
package leetcode
// 在排序数组中查找元素的第一个和最后一个位置
// 直接遍历查找
func searchRange1(nums []int, target int) []int {
j := -1
for i, v := range nums {
if v == target {
j = i
break
}
}
k := j
for i := j + 1; i < len(nums) && nums[i] == target; i++ {
k = i
}
return []int{j, k}
}
// 遍历查找，另一种写法
func searchRange3(nums []int, target int) []int {
res := []int{-1, -1}
for i, v := range nums {
if v == target {
if i == 0 || nums[i-1] != target {
res[0] = i
}
if i == len(nums)-1 || nums[i+1] != target {
res[1] = i
}
}
}
return res
}
// 二分查找
func searchRange2(nums []int, target int) []int {
lo, hi := 0, len(nums)-1
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] > target {
hi = mid - 1
} else if nums[mid] < target {
lo = mid + 1
} else {
if nums[lo] == target && nums[hi] == target {
return []int{lo, hi}
}
if nums[lo] != target {
lo++
}
if nums[hi] != target {
hi--
}
}
}
return []int{-1, -1}
}
你可能感兴趣的文章
0
赞
热门推荐
-
2、 - 优质文章
-
3、 gate.io
-
8、 golang
-
9、 openharmony
-
10、 Vue中input框自动聚焦