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

佚名 6年前 (2019-04-14) 随笔 1945人围观抢沙发百度已收录

题目描述

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

分析

因为是一个排序数组，所以利用二分查找，找出第一个k值和最后一个k值，再相减差值+1就是出现的次数。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

贴出代码

public class Solution {
    public int GetNumberOfK(int [] array , int k) {
        if(array == null || array.length == 0){
            return 0;
        }
        int first = getFirstK(array, k, 0, array.length - 1);
        int last = getLastK(array, k, 0, array.length - 1);
        if(first == -1 || last == -1){
            return 0;
        }
        else{
            return last - first + 1;
        }
    }
    
    public int getFirstK(int[] array, int k, int start, int end){
        while(start <= end){
            int mid = (start + end) / 2;
            if(k < array[mid]){
                end = mid - 1;
            }else if(k > array[mid]){
                start = mid + 1;
            }
            else{
                if((mid > 0 && array[mid - 1] != k) || mid == 0){
                    return mid;
                }else{
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
    
    public int getLastK(int[] array, int k, int start, int end){
        while(start <= end){
            int mid = (start + end) / 2;
            if(k < array[mid]){
                end = mid - 1;
            }else if(k > array[mid]){
                start = mid + 1;
            }
            else{
                if((mid < array.length - 1 && array[mid + 1] != k) || mid == array.length -1){
                    return mid;
                }
                else{
                    start = mid + 1;
                }
            }
        }
        return -1;
    }
}