数字在排序数组中出现的次数（剑指offer）利用快排思想（O（logn））

题意：首先数组是个已经排列的有序递增序列！统计一个数出现的次数，相当于在有序的序列里插入一个数，那么我只要确定插入的位置，利用快排的思想，也可以说是二分，如果在数组中找到k，那么左右拓展边界就可以确定，该数在数组中出现的次数了。

一些特殊情况可以特判！比如k小于数组最小数，或者大于数组最大数；

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()<=0) return 0;
        if(data[0]>k || data[data.size()-1]<k) return 0;
        int left=0;
        int right=data.size()-1;
        int x=0,y=0,len=right;
        bool bo=false;
        while(left<=right)
        {
            int mid=(left+right)/2;
            if(data[mid]==k)
            {
                bo=true;
                x=y=mid;
                while(y+1<=len && data[y+1]==k) ++y;
                while(x-1>=0  && data[x-1]==k) --x;
                break;
            }
            if(data[mid]>k)
            {
                right=mid-1;
            }
            else if(data[mid]<k)
            {
                left=mid+1;
            }
        }
//        printf("x=%dty=%dn",x,y);

        if(bo) return y-x+1;
        else return 0;
    }
};

最后

以上就是整齐洋葱为你收集整理的数字在排序数组中出现的次数（剑指offer）利用快排思想（O（logn））的全部内容，希望文章能够帮你解决数字在排序数组中出现的次数（剑指offer）利用快排思想（O（logn））所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。