统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
限制：
0 <= 数组长度 <= 50000
二分查找
/**
* 二分查找
*
* @param nums
* @param target
* @return
*/
public static int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return 0;
int cnt = 0;
int left = 0, right = nums.length - 1;
int mid = left;
while (left <= right) {
mid = (left + right) >> 1;
if (nums[mid] == target) break;
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
int index = mid;
// 左侧
while (index >= 0 && index < nums.length && nums[index] == target) {
cnt++;
index--;
}
index = mid + 1;
// 右侧
while (index >= 0 && index < nums.length && nums[index] == target) {
cnt++;
index++;
}
return cnt;
}
测试用例
public static void main(String[] args) {
int[] nums = new int[]{0};
int target = 0;
int cnt = SearchSecond.search(nums, target);
System.out.println("SearchSecond demo01 result : " + cnt);
nums = new int[]{5, 7, 7, 8, 8, 10};
target = 8;
cnt = SearchSecond.search(nums, target);
System.out.println("SearchSecond demo02 result : " + cnt);
nums = new int[]{5, 7, 7, 8, 8, 10};
target = 6;
cnt = SearchSecond.search(nums, target);
System.out.println("SearchSecond demo03 result : " + cnt);
nums = new int[]{1, 2, 3, 3, 3, 3, 4, 5, 9};
target = 3;
cnt = SearchSecond.search(nums, target);
System.out.println("SearchSecond demo04 result : " + cnt);
nums = new int[]{1, 2, 3};
target = 1;
cnt = SearchSecond.search(nums, target);
System.out.println("SearchSecond demo05 result : " + cnt);
}
运行结果
