题目描述

统计⼀个数字在升序数组中出现的次数。

示例1 输⼊：[1,2,3,3,3,3,4,5],3 返回值：4

思路及解答

线性遍历

顺序遍历数组，遇到目标值就计数

  • 时间复杂度​：O(n)，最坏情况下需要遍历整个数组

  • ​空间复杂度​：O(1)，只使用常数级别额外空间

二分查找+左右扫描法

先使用二分查找定位到目标值，然后向两边扩展统计。

由于数组是有序的，可以明显看到是二分法。

第1步是找出数值为 k 的数的索引： 假设数组为 nums[]，⼀开始的左边索引为 left = 0，右边界索引为 right = nums.length-1

  1. 将数组分成两部分，中间的数为 nums[mid] 。第1部分为 [left,mid] ,第2部分为[mid+1,right]。

  2. 如果 nums[mid]>k ,则说明 k 只可能存在前半部分中，对前半部分执⾏操作1。

  3. 如果 nums[mid]<k ,则说明 k 只可能存在后半部分中，对后半部分执⾏操作1。

  4. 如果 nums[mid]=k ,直接返回当前索引 mid 。

  5. 如果 left > right ,说明 k 不存在，则返回 -1 。

找到索引之后，往两边扩展，同时统计k的个数，直到元素不等于 k 的时候停⽌。

  • ​时间复杂度​：O(log n + k)，其中k是目标值出现次数。当目标值出现次数较少时效率接近O(log n)，但最坏情况（全部是目标值）退化为O(n)

  • ​空间复杂度​：O(1)

双二分查找法（推荐）

分别使用二分查找找到目标值的起始和结束位置，计算区间长度，这是最优解法。

  • ​时间复杂度​：O(log n)，执行两次二分查找

  • ​空间复杂度​：O(1)，只使用常数空间

k±0.5边界查找法

一种巧妙的解法，通过查找目标值边界的插入位置来计算出现次数。

由于数组元素都是整数，k-0.5和k+0.5正好是目标值范围的边界，它们的插入位置差值就是目标值出现次数。

  • ​时间复杂度​：O(log n)，两次二分查找

  • ​空间复杂度​：O(1)