數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)

題目描述

統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。

public class Solution {
    /*解題思路：
    有序數(shù)組的問題，采用二分查找。找到第一個K和最后一個K，兩者的位置相減
    */
    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){//重點array[mid-1] == k
            return getFirstK(array, k, start, mid-1);
        }else{
            return mid;
        }
    }
    //循環(huán)寫法
    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){
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else if(mid+1 < length && array[mid+1] == k){//重點array[mid+1] == k
                start = mid+1;
            }else{
                return mid;
            }
            mid = (start + end) >> 1;
        }
        return -1;
    }
}