数字在排序数组中出现的次数

问题描述

统计一个数字在排序数组中出现的次数。

思路分析(解法一)

最直观的想法就是通过顺序查找，即依次比较数组与给定元素大小，然后设置一个计数变量，又由于数组是排序的，所以直接当比较的数大于给定数时，结束

码上有戏

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

思路分析(解法二)

由于是已排序的，所以查找最好的就是通过二分查找，即先找出第一次出现和最后一次出现该数即可，但是由于当我们找到该数时，比如第一次找到该数时，先比较在他前面是否有重复该数，如果是，这说明据需向前面比较，知道找到第一次出现该数，同理，最后一次出现该数也是比较后面是否有该数重复

码上有戏

public int GetNumberOfK(int [] array , int k) {
    int length = array.length;
         if(length == 0){
             return 0;
         }
         int firstK = getFirstK(array, k, 0, length-1);
         int lastK = getLastK(array, k, 0, length-1);
         if(firstK != -1 && lastK != -1){
              return lastK - firstK + 1;
         }
         return 0;
 }
 
 private int getFirstK(int array[],int k,int start,int end){
   if(start>end)return -1;
    int mid=(start+end)>>1;
   if(array[mid]>k)return getFirstK(array,k,start,mid-1);
   else if(array[mid]<k) return getFirstK(array,k,mid+1,end);
       else if(mid-1 >=0 && array[mid-1] == k){
           return getFirstK(array, k, start, mid-1);
       }
   else return mid;
 }
 
 private int getLastK(int array[],int k,int start,int end){
       int length = array.length;
   int mid=(start+end)>>1;
   while(start<=end){
     if(array[mid]<k)
       start=mid+1;
     else if(array[mid]>k)
       end=mid-1;
           else if(mid+1 < length && array[mid+1] == k){
               start = mid+1;
           }
     else 
       return mid;
     mid=(start+end)>>1;
   }
   return -1;
 }