1：时间复杂度为o(N)的情况
private static int countNumber(int[] array, int number) {
if (array == null || array.length <= 0) {
return 0;
}
int count = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == number) {
count++;
}
}
return count;
}
这个不符合有序数组的要求，有序数组一般优先考虑到二分查找
2：时间复杂度o(logN)
总体的思路是：找到第一个出现的位置，然后从该位置起分别向左和向右查找
2.1:二分查找
private static int binarySearch(int[] array, int start, int end, int number) {
if (array == null || array.length <= 0 || (start == end && array[start] != number)) {
return 0;
}
int middle = (start + end) / 2;
if (array[middle] > number) {
binarySearch(array, start, middle -1, number);
} else if (array[middle] < number) {
binarySearch(array, middle + 1, end, number);
} else {
return middle;
}
return -1;
}
首先通过二分查找找到第一个出现的位置
2.2:分别从当前位置向前和向后查找
private static int findNumberCount(int[] array, int number) {
if (array== null || array.length <= 0) {
return 0;
}
int pos = binarySearch(array, 0, array.length -1, number);
if (pos == -1) {
return 0;
}
/* 从第一次的位置分别向前和向后查找*/
int count = 0;
for (int i = pos; i > 0 && array[i] == number; i--) {------>向前(左)查找
count++;
}
for (int i = pos + 1; i < array.length && array[i] == number; i++) {---->向后(右)查找
count++;
}
return count;
}
