题目描述
统计一个数字在排序数组中出现的次数。
例如输入排序数组$ [1,2,3,3,3,3,4,5]$和数字$ 3$,由于$ 3$在这个数组中出现了$ 4$次,因此输出$ 4$。
数据范围
数组长度 $[0,1000]$。
样例
输入:
[1, 2, 3, 3, 3, 3, 4, 5] , 3
输出:4
算法
二分法
使用两次二分分别算出第一个$>=k$的位置和最后一个$>=k$的位置分别几位$start$和$end$,$end-start+1$即为答案
注意要判断下特殊条件
- 1.空数组,直接返回0
- 2.$k$不存在于$nums$中,那么第一次二分查出来的数就不会等于$k$,特判一下,直接返回0即可
时间复杂度
$O(n*logn)$
Java 代码
class Solution {
public int getNumberOfK(int[] nums, int k) {
if (nums.length == 0) {
return 0;
}
int l = 0, r = nums.length - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (nums[mid] > k) {
r = mid - 1;
} else {
l = mid;
}
}
int end = r;
if (nums[r] != k) {
return 0;
}
l = 0; r = nums.length - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= k) {
r = mid;
} else {
l = mid + 1;
}
}
return end - r + 1;
}
}