在排序数组中，找出给定数字的出现次数

编程技术  /  houtizong 发布于 3年前   49

public class CountTimesInSortedArray {/** * 题目：在排序数组中，找出给定数字的出现次数，比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。 * 解法：使用二分查找的方法分别找出给定数字的开始和结束位置，最坏情况下时间复杂度为O(logn) */public static void main(String[] args) {int[] data={0,1,2,2,3,3,3,4,4,4,4,5};for(int target:data){int time=times(data,target);System.out.println(target+","+time+" times");}}public static int times(int[] array,int target){if(array==null||array.length==0){return -1;}return upTimes(array,target)-downTimes(array,target)+1;}public static int upTimes(int[] array,int target){int low=0;int high=array.length-1;while(low<high){int mid=(low&high)+(low^high)/2+1;//when low=high-1,let mid=highint value=array[mid];if(value<=target){low=mid;}else{high=mid-1;}}return low;}public static int downTimes(int[] array,int target){int low=0;int high=array.length-1;while(low<high){int mid=(low&high)+(low^high)/2;//when low=high-1,let mid=lowint value=array[mid];if(value>=target){high=mid;}else{low=mid+1;}}return low;}}