剑指offer(C++)-JZ53：数字在升序数组中出现的次数(算法-搜索算法)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数

数据范围：0≤n≤1000,0≤k≤100，数组中每个元素的值满足 0≤val≤100
要求：空间复杂度 O(1)，时间复杂度 O(logn)

示例：

输入：

[1,2,3,3,3,3,4,5],3

返回值：

4

解题思路：

本题考察算法-搜索算法的使用。考虑到复杂度的要求，采用二分法的思路解题。具体实现列了三种写法：

解法一：二分查找

1. 因题目中全是整数，此时可以将k加减一个小数，达到错位的目的。
2. BinarySearch(data, k + 0.1)得到的是目标值最后一次出现位置的右侧，BinarySearch(data, k - 0.1)得到的是目标值首次出现的位置，相减刚好是出现的次数。
3. BinarySearch函数执行二分查找，当左边界超过了右边界，说明此时的左边界是目标值的位置向上取整。

解法二：STL内置二分搜索算法-equal_range

1. result是一个pair,里面存放了两个迭代器。
2. first表示k首次出现的位置，second表示k最后一个出现位置的下一个位置。

解法三：模拟STL内置函数-lower_bound&upper_bound

1. lower_bound寻找该值首次出现的位置。
2. upper_bound寻找该值最后一次出现的位置，返回该位置的后一位。

测试代码：

解法一：二分查找

class Solution {
public:
    // 二分查找
    int BinarySearch(vector<int>& data, float k)
    { 
        int left = 0;
        int right = data.size() - 1;
        // 确定目标的左右边界
        // 当左边界超过了右边界，说明此时的左边界是目标值的位置向上取整
        while(left <= right)
        { 
            int mid = (left + right) / 2;
            if(data[mid] < k)
                left = mid + 1;
            else if(data[mid] > k)
                right = mid - 1;
        }
        return left;
    }
    
    // 寻找目标值
    int GetNumberOfK(vector<int> data ,int k) 
    {
        // 因题目中全是整数，此时可以将k加减一个小数，达到错位的目的
        // BinarySearch(data, k + 0.1)得到的是目标值最后一次出现位置的右侧
        // BinarySearch(data, k - 0.1)得到的是目标值首次出现的位置
        // 相减刚好是出现的次数
        return BinarySearch(data, k + 0.1) - BinarySearch(data, k - 0.1);
    }
};

解法二：equal_range

class Solution {
public:
    // 寻找目标值
    int GetNumberOfK(vector<int> data ,int k) 
    {
        // result是一个pair,里面存放了两个迭代器
        // first表示k首次出现的位置，second表示k最后一个出现位置的下一个位置
        auto result = equal_range(data.begin(), data.end(),k);
        return result.second - result.first;
    }
};

解法三：lower_bound&upper_bound

class Solution {
public:
    // 寻找目标值
    int GetNumberOfK(vector<int> data ,int k) 
    {
        // 寻找该值首次出现的位置
        int first = LowerBound(data, k);
        // 寻找该值最后一次出现的位置，返回该位置的后一位
        int second = UpperBound(data, k);
        return second - first;
    }
    
    // 寻找该值首次出现的位置
    int LowerBound(vector<int>& data, int k)
    {
        int l = 0, r = data.size();
        while(l<r)
        {
            int m = (l+r)/2;
            if(data[m]>=k)
                r = m;
            else
                l = m+1;
        }
        return l;
    }
    
    // 寻找该值最后一次出现的位置，返回该位置的后一位
    int UpperBound(vector<int>& data, int k)
    {
        int l = 0, r = data.size();
        while(l<r)
        {
            int m = (l+r)/2;
            if(data[m]>k)
                r = m;
            else
                l = m+1;
        }
        return l;
    }
};