题目描述

描述:

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

示例1 输入： [1,2,3,3,3,3,4,5],3
返回值： 4

题解1:暴力法,遍历数组中所有的元素

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
//         题解1:暴力法
        int count = 0;
        for(int i = 0;i<data.size();i++){
            if(data[i] == k){
                count++;
            }
        }
        return count;  
    }
};

题解2:通过二分法找到元素k在数组中下标最小的位置和小标最大的位置处

图示如下,图为某位大佬的图示,在此借鉴:

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        //题解2:通过二分法分别找到元素k在数组中的下标最小处位置和下标最大处的位置
        int lowBound = 0;//下界限
        int largeBound = 0;//上界限
        int left = 0;
        int right =data.size()-1;
        //找到元素k在数组中下标最小处的位置
        while(left <= right){
            int mid = (left + right)/2;
            if(data[mid] > k)
                right = mid-1;
            else if(data[mid] <k )
                left = mid+1;
            else{//找到了元素k所在的位置
                lowBound = largeBound = mid;
                while(data[lowBound] == k)
                    lowBound--;//当元素k重复时,下标界-1
                while(data[largeBound] == k)
                    largeBound++;//当元素k重复时,上标界-1
                return largeBound - lowBound -1;//边界相减,得到重复元素个数
            }
        }
        return 0;
        
    }
};