题目:统计一个数字在排序数组中出现的次数。
思路:因为数组是有序的,二分法思想;先找到相等的位置,再分别往前和往后找。
代码:
public class OneOnArrayTimes {
public static void main(String[] args) {
OneOnArrayTimes oat=new OneOnArrayTimes();
int []a= {1,3,3,3,5};
System.out.println(oat.GetNumberOfK(a,3));
}
public int GetNumberOfK(int[] array, int k) {
int low = 0;
int high = array.length - 1;
int mid = (low + high) / 2;
int count = 0;
while (low <= high) {
if (array[mid] > k) {
high = mid - 1;
} else if (array[mid] < k) {
low = mid + 1;
} else {
count++;
break;
}
mid = (low + high) / 2;
}
int temp = mid;// 记录相等的位置
while (--temp >= 0) {
if (array[temp] != k) {
break;
}
count++;
}
temp = mid;// 记录相等的位置
while (++temp <= array.length - 1) {
if (array[temp] != k) {
break;
}
count++;
}
return count;
}
}