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

本文为剑指 offer 系列第三十六篇。
主要知识点为二分查找,但是可以偷懒用stl来解决掉。

题目描述

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

解题思路

思路1

直接使用stl的count方法

思路2

先使用stl的find方法找到第一个值，然后向后遍历计数

思路3

利用二分查找，先找到第一个大于这个val的索引，然后找到小于这个val的最大的索引，做差然后减去1就是这个值出现的次数。

解题代码

思路1代码

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        // 方法1 使用stl的count
        return count(data.begin(),data.end(),k);
    }
};

时间复杂度为O(logn),空间复杂度为O(1)

思路2代码

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {

        //方法2  使用stl的find
        auto a = find(data.begin(),data.end(),k);
        if(a == data.end()){
         return 0;
        }else{
          int res = 0;
           while(*a == k){
               res++; a++;
           }
           return res; 
    }

};

时间复杂度为O(logn),空间复杂度为O(1)

思路3代码

// 暂时还没有写好，等我写好再来补充。

时间复杂度为O(n),空间复杂度为O(1)
以上，本题结束！