53.数字在排序数组中出现的次数（简单）

考点：本题考查知识迁移能力

题目一描述

统计一个数字在排序数组中出现的次数。
输入: array= [5,7,7,8,8,10], k= 8
输出: 2

思路一：暴力法遍历整个数组

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++;
       }
        return count;
    }
}

思路二：二分查找

由于数组是一个排序过的数组，所以可以用二分查找法

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array==null||array.length<=0||k<array[0]||k>array[array.length-1])
            return 0;
        return getK(array,k,0,array.length-1);
       
    }
    private int getK(int[] array, int k, int start, int end){
        if(start > end)
            return 0;
        int mid = (end - start)/2 + start;
        if(array[mid]>k){
            return getK(array,k,start,mid-1);
        }
        else if(array[mid]<k){
            return getK(array,k,mid+1,end);
        }
        else{
            return getK(array,k,start,mid-1)+getK(array,k,mid+1,end)+1;
        }
    }
}

题目二描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出0～n-1中缺失的数字。
输入: [0,1,2,3,4,5,6,7,9]
输出: 8

思路：二分查找

0～n-1这些数字在数组中是排序的，如果不在数组中的那个数字是m，那么所有比m小的数字的下标都与它们的值相同，m正好是数组中第一个数值和下标不相等的下标。

class Solution {
    public int missingNumber(int[] nums) {
        if(nums==null||nums.length<=0)
            return -1;
        int start = 0;
        int end = nums.length-1;
        while(start<=end){
            int mid = (end - start)/2 + start;
            if(nums[mid]!=mid){
                if(mid==0||nums[mid-1]==mid-1)
                    return mid;
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
            if(start == nums.length)
                return nums.length;
           
        }
         return -1;
    }
}