数字在排序数组中出现的次数（剑指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））的全部内容，更多相关数字在排序数组中出现内容请搜索靠谱客的其他文章。