剑指Offer 38 数字在排序数组中出现的次数

题目描述

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

思路

暴力法其实也很简单 O（n）的复杂度，但是谁让我们厉害呢

优化其实也就是两个二分，一个找开始，一个找结束，注意边界值的就好了

代码

static   public int GetNumberOfK(int [] array , int k) {
        if (array==null||array.length==0)
            return  0;
            int first =GetFirst(array,k,0,array.length-1);
            int last = GetLast(array,k,0,array.length-1);
      return (first>-1&&first>-1)?last-first+1:0;
    }
  static   public  int GetFirst(int []arr,int k ,int  start , int end)
    {
        if (start>end)
            return  -1;
        int mid = (start+end)>>1;
        if (arr[mid]==k)
        {
            if ((mid==0)||(mid>0&&arr[mid-1]!=k))
            {
                return mid;
            }
            else
                end = mid-1;
        }
        else if (arr[mid]<k)
        {
            start=mid+1;
        }
        else if (arr[mid]>k)
            end = mid-1;
        return GetFirst(arr,k,start,end);
    }
  static   public  int GetLast(int []arr,int k ,int  start , int end)
    {
            if (start>end)
                return -1;
            int mid = (start +end)>>1;
        if (arr[mid]==k)
        {
            if (mid==arr.length-1||(mid<arr.length-1&&arr[mid+1]!=k))
                return mid;
            else
                start= mid+1;
        }
        else if (arr[mid]>k)
            end=mid-1;
        else if (arr[mid]<k)
            start = mid+1;
        return GetLast(arr, k, start, end);
    }

收获

其实没什么收获的啦，心静心静；

2017-04-02