首页 > 编程语言 > 详细

剑指offer37-数字在排序数组中出现的次数

时间:2020-02-24 22:05:08      阅读:73      评论:0      收藏:0      [点我收藏+]

题目描述

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

思路:

最简单的从头遍历

更优化的方案利用二分法。

我做的时候,一开始在while循环里面忘记mid=(begin+end)/2,导致运行时间超长进入死循环。粗心啊!!!

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //给你一个有序的数组,找到k出现的次数
        int len = data.size();
        if(len==0) return 0;
        int begin = 0;
        int end = len-1;
        int mid = (begin+end)/2;
        int count = 0;
        while(end>=begin){
            mid = (begin+end)/2;
            if(data[mid]==k){
                for(int i=begin;i<=end;i++){
                    if(data[i]==k)
                        count++;
                }
                break;
            }
            else if(data[mid]>k){
                end = mid-1;
            }
            else{
                begin = mid+1;
            }
        }
        return count;
    }
};

 

剑指offer37-数字在排序数组中出现的次数

原文:https://www.cnblogs.com/loyolh/p/12358887.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!