题目
统计一个数字在排序数组中出现的次数。
解题思路
- 通过二分查找分别找到 n 的第一个位置和最后一个位置
- 再进行计算就可以得出结果
public int countOfSortedArray2(int[] nums, int n) {
if (nums == null || nums.length == 0) return 0;
int firstN = getFirstN(nums, n);
int lastN = getLastN(nums, n);
return lastN - firstN + 1;
}
private int getFirstN(int[] nums, int n) {
int s = 0, e = nums.length - 1;
int mid = -1;
while (s <= e) {
mid = (s + e) / 2;
if (mid > 0 && nums[mid - 1] == n) {
e = mid - 1;
continue;
}
if (nums[mid] > n) {
e = mid - 1;
continue;
}
if (nums[mid] < n) {
s = mid + 1;
continue;
}
break;
}
return mid;
}
private int getLastN(int[] nums, int n) {
int s = 0, e = nums.length - 1;
int mid = -1;
while (s <= e) {
mid = (s + e) / 2;
if (mid < nums.length - 1 && nums[mid + 1] == n) {
s = mid + 1;
continue;
}
if (nums[mid] > n) {
e = mid - 1;
continue;
}
if (nums[mid] < n) {
s = mid + 1;
continue;
}
break;
}
return mid;
}