Q1036.md

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

题目：

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

---

我的代码

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

思路分析

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
       int number=0;
        if(array!=null&&array.length>0){
            int first=GetFirstK(array,array.length,k,0,array.length-1);
            int last=GetLastK(array,array.length,k,0,array.length-1);
            if(first>-1&&last>-1)
                number=last-first+1;
        }
        return number;
    }
    
    private int GetFirstK(int[] array,int length,int k,int start,int end){
        if(start>end) return -1;
        int middleIndex=(start+end)/2;
        int middleData=array[middleIndex];
        if(middleData==k){
            if((middleIndex>0&&array[middleIndex-1]!=k)||middleIndex==0){
                return middleIndex;
            }
            else
                end=middleIndex-1;
        }
        else if(middleData>k)
            end=middleIndex-1;
        else
            start=middleIndex+1;
        return GetFirstK(array,array.length,k,start,end);
    }
    
    private int GetLastK(int[] array,int length,int k,int start,int end){
        if(start>end) return -1;
        int middleIndex=(start+end)/2;
        int middleData=array[middleIndex];
        if(middleData==k){
            if((middleIndex<length-1&&array[middleIndex+1]!=k)||middleIndex==length-1)
                return middleIndex;
            else
                start=middleIndex+1;
        }
        else if(middleData<k)
            start=middleIndex+1;
        else
            end=middleIndex-1;
        return GetLastK(array,array.length,k,start,end);
    }
}