题解 | #数字在升序数组中出现的次数#

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

http://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //如果二分查找过程中遇到的当前数不是k则按照正常的二分方法继续递归
        //如果当前遇到的数等于k则要在两边继续二分这样才能找到所有的k
        int high=data.size();
        return process(data, 0, high-1, k);
        
    }
    //该递归函数的意思是在low到high的范围上返回k出现的次数
    int process(vector<int> array,int low,int high,int k)
    {
        if(low>high)//base case
            return 0;
        int ans=0;
        int mid=(low+high)/2;//因为数据范围较小,所以不用担心low+high会越界
        if(array[mid]<k){//第一种情况:当前数小于k则按照正常的递归套路就行
            ans+=process(array,mid+1,high,k);
        }
        if(array[mid]>k){//第二种情况也是正常情况:也按照递归套路求解即可
            ans+=process(array, low, mid-1, k);
        }
        if(array[mid]==k)//第三种情况:此时应该向两边继续递归
        {
            ans++;//首先ans++,因为此时已经找到一个k了
            ans+=process(array, low, mid-1, k);
            ans+=process(array, mid+1, high,k);
        }
        return ans;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 18:02
好不容易拿到了字节Offer,鼠鼠做后端的,但家里人觉得可能被裁员不稳定,让鼠鼠去投国企,现在好纠结到底该咋选
文档传偷助手:该投就投吧,不过建议别放弃offer 拿到手里的才是最好的
投递字节跳动等公司8个岗位
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务