53.md

数字在升序数组中出现的次数

题目

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

要求：空间复杂度 O(1)，时间复杂度 O(logn)

示例

输入：[1,2,3,3,3,3,4,5],3

返回值：4

思路

• 暴力遍历是可以，但是面试官不开心
• 利用数组升序的特点使用二分查找
• 目标值如果有多个，肯定是连在一起
• 首先找到一个目标，再顺着两头数
• 或者可以先找上下边界
• 上界定义为：不管目标值存在与否，都指向大于目标值的第一个值
• 下界定义为：如果存在目标值，则指向第一个目标值，否则，如果不存在， 则指向大于目标值的第一个值
• 最后的结果就是：上界下标 - 上界下标

实现

package main

// 数字在升序数组中出现的次数
func main() {
	num := []int{1, 2, 3, 3, 3, 3, 4, 5}
	size := 3
	GetNumberOfK(num, size)
}

func GetNumberOfK(data []int, k int) int {
	cur := 0
	end := len(data)
	for {
		if cur >= end {
			break
		}
		mid := cur + (end-cur)/2
		if data[mid] < k {
			cur = mid + 1
		} else {
			end = mid
		}
	}
	lbound := cur
	cur = 0
	end = len(data)
	for {
		if cur >= end {
			break
		}
		mid := cur + (end-cur)/2
		if data[mid] <= k {
			cur = mid + 1
		} else {
			end = mid
		}
	}
	rbound := cur
	return rbound - lbound
}