《剑指offer》 第53.1题 数字在排序数组中的出现的次数

题目描述
统计一个数字在排序数组中出现的次数。
比如给定{1,2,3,4,4,4,4,5,6} 和4，能知道4出现了4次。

常规解法，遍历一次，，找到元素，然后统计次数，时间复杂度O(n)，但是又想到排序，就可以使用二分，显然时间复杂度只有O(logn)。

解法1：

首先遍历，找元素，找到后，每碰到一个相同的元素，count++。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        int count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==k)
                count++;
        }
        return count;
    }
}

解法2：

  一旦有排序好数组，就可以想到使用二分法。这里通过二分法找到该元素后，由于可能出现多次，因此，需要找到第一次出现的时候，和最后一次出现的时候，然后做差值，就是次数。
注意细节：在对某个范围进行二分后，需要判断是否应当继续二分。因此用mid == K来判断，此时有三种情况，等于，小于，大于。显然小于和大于都很好处理，直接缩减范围就行，而等于时，需要考虑更多，比如在调用getFirstK时，mid=K，那么需要考虑其左边是否还有K，如果还有K，则继续调用getFirstK，如果没有K,说明找到了第一个K，就应当返回，但是特殊情况在于，当前的K可能是最左边的元素，此时K左边没有数了（无法进行和左边的数进行比较这一操作），所以还需要判断，K是否为索引为0的数。因此在等于时会稍微复杂一些。同理，在getLastK时，相等需要判断是否达到了最右边。

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length<=0)
            return 0;
         int firstK = getFirstK(array, 0, array.length-1, k);
         int lastK = getLastK(array, 0, array.length-1, k);
         if(firstK > -1 && lastK > -1)//如果左右都是-1，说明没有找到K，应该直接返回0
            return lastK - firstK + 1;//找到了，就做差+1
         return 0;
     }

     private int getFirstK(int[] arr, int start, int end,int k){
         if(start>end)//递归结束条件(说明没有左边没有找到k)
             return -1;
         int mid = (start+end)/2;//将当前数组一分为二
         if(arr[mid]==k){//如果中间的恰好等于,需要分类讨论
             if( mid == 0 ||arr[mid-1]!=k )//等于K，且中间的索引是0或者其左边不是K
                 return mid;//就说明mid就是最左边的了，直接返回
             else
                 end = mid-1;//索引不是0，且左边还是K，那就得在左边缩小范围
         }else if(arr[mid]<k){//小于，就说明还在右边
             start = mid+1;
         }else{//大于，就说明在左边，左边需要缩小范围（这里是不同的时候，上面的是相同）
             end = mid-1;
         }
         return getFirstK(arr,start,end,k);
     }

     private int getLastK(int[] arr, int start, int end,int k){
         if(start>end)//说明右边没有找到K
             return -1;
         int mid = (start+end)/2;//将当前数组一分为二
         if(arr[mid]==k){//相同，需要看右边还有没有相同的
             if(mid==arr.length-1 || arr[mid+1]!=k )//要么是边界，要么是最后一个
                 return mid;
             else //相等，既不是右边界，又不是最后一个，对右边缩小范围
                 start = mid+1;
         }else if(arr[mid]<k){//中间的小于k,说明还在右边
             start = mid+1;
         }else{//中间大于k，说明在左边
             end = mid-1;
         }
         return getLastK(arr,start,end,k);
     }
}