题目描述

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

题目解答

public class Solution {    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){ //k在左边            return getFirstK(array,k,start,mid-1);        }else if(array[mid]
       
        =0 && array[mid-1]==k){ //mid的前一个为k，k在左边            return getFirstK(array,k,start,mid-1);        }else{ //mid前一个不为k，mid为k，k恰好是第一个mid            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){
     //k在左边                end=mid-1;            }else if(array[mid]
        
         >1;        }        return -1;    }}