1：時間復(fù)雜度為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;
}
這個不符合有序數(shù)組的要求嵌器，有序數(shù)組一般優(yōu)先考慮到二分查找
2：時間復(fù)雜度o(logN)
總體的思路是：找到第一個出現(xiàn)的位置，然后從該位置起分別向左和向右查找
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;
}
首先通過二分查找找到第一個出現(xiàn)的位置
2.2:分別從當(dāng)前位置向前和向后查找
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;
}
