LeetCode 剑指 Offer 53 - I. 在排序数组中查找数字 I
题目描述
给定一个排序数组
nums和一个目标值target，请你在数组中查找目标值target的出现次数。如果target不存在于数组中，则返回 0。
示例 1： 输入：
nums = [5, 7, 7, 8, 8, 10],target = 8输出：2解释：8在数组中出现了两次。
示例 2： 输入：
nums = [5, 7, 7, 8, 8, 10],target = 6输出：0解释：6在数组中不存在。
提示：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
思路分析
思路描述
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 查找目标值的左边界
func findLeft(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
// 查找目标值的右边界
func findRight(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] <= target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
func search(nums []int, target int) int {
left := findLeft(nums, target)
right := findRight(nums, target)
return right - left
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 查找目标值的左边界
func findLeft(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
// 查找目标值的右边界
func findRight(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] <= target {
left = mid + 1
} else {
right = mid - 1
}
}
return left
}
func countTarget(nums []int, target int) int {
left := findLeft(nums, target)
right := findRight(nums, target)
return right - left
}
1
write your code here
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！