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

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

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

题目中要求时间复杂度O(logn),所以直接用二分查找。
总体思路是通过二分查找找到要找的数,然后在查找该数周围相同的数,最后返回累计计数。复杂度满足题目要求。
因为写完一次过了,所以代码结构还有较大调整空间。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        int index;
        int left = 0;
        int right = data.size() - 1;
        while(right >= left){
            int mid = left + (right - left)/2;
            if(data.at(mid) == k){
                index = mid;
                break;
            }
            else if(data.at(mid) > k){
                right = mid - 1;
            }
            else{
                left = mid + 1;
            }
        }
        if(right < left){
            return 0;
        }
        for(int i = index;i < data.size();i++){
            if(data.at(i) == k){
                count++;
            }
            else{
                break;
            }
        }
        if(index > 0){
            for(int i = index - 1;i >= 0;i--){
                if(data.at(i) == k){
                    count++;
                }
                else{
                    break;
                }
            }
        }
        return count;
    }
};
全部评论

相关推荐

2024-12-25 09:09
四川师范大学 运营
想和你交朋友的潜伏者要冲国企:先去沃尔玛亲身感受标准化流程体系,一两年后再跳槽国内任何零售行业,可以有更大选择权吧?
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务