1.遍历法。无代码。
2.二分法。二分查找元素,然后二分查找左边界,再查找右边界,最后右边界减去左边界就是指定元素个数。这道题实际上是如下三道题的综合。
- 在一个有序数组中,找某个数是否存在 。
- 在一个有序数组中,找>=某个数最左侧的位置 。
- 在一个有序数组中,找<=某个数最右侧的位置 。
golang代码如下:
package main
import "fmt"
func main() {
arr := []int{0, 1, 2, 3, 3, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8}
v := 3
fmt.Println(v, "的个数是:", BSCount(arr, v))
}
//二分法
func BSCount(arr []int, v int) int {
L := 0
R := len(arr) - 1
M := -1
// L..R
mid := -1
//找目标值并且缩小左边界L和右边界R的范围
for L <= R {
mid = L + (R-L)>>1
if arr[mid] == v {
M = mid
break
} else if arr[mid] > v {
R = mid - 1
} else {
L = mid + 1
}
}
//没找到目标值,直接返回
if M == -1 {
return 0
}
index := 0
LL := L //缓存原始左边界
RR := R //缓存原始右边界
//找左边界
R = M //缩小范围
for L <= R {
mid = L + (R-L)>>1
if arr[mid] >= v {
index = mid
R = mid - 1
} else {
L = mid + 1
}
}
LL = index //左边界确定下来了
R = RR //原始右边界已经发生变化,需要恢复到以前的边界
//找右边界
L = M //缩小范围
for L <= R {
mid = L + (R-L)>>1
if arr[mid] <= v {
index = mid
L = mid + 1
} else {
R = mid - 1
}
}
RR = index //右边界确定下来了
return RR - LL + 1
}
执行结果如下: