题目描述

blablabla

样例

剑指

算法1

(二分查找) $O(logn)$

blablabla

时间复杂度分析：0(logn)

C++ 代码

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        if (nums.size() == 0) return NULL;
        int number = 0;
        int length = nums.size();       
        int start = 0, end = length-1;
        int first = Getfirst(nums, start, k, end);
        int last = Getlast(nums, start, k, end);
        //cout << first << ' ' << last << endl;
        if (first > -1 && end > -1)
        number = last - first + 1;
        return number;
    }
        int Getfirst (vector<int>& nums, int start, int k, int end){
            if (start > end) return -1;
            int mid = (start + end) / 2;
            int middata = nums[mid];
            if (middata == k) {
            if (mid > 0&&nums[mid-1] != k || mid == 0)
                return mid;
            else end = mid - 1;            
            }
            else if(middata < k) start = mid+1;
            else end = mid-1;
            return Getfirst(nums, start, k, end);
        }
        int Getlast (vector<int>& nums, int start, int k, int end){
            if (start > end) return -1;
            int length = nums.size(); 
            int mid = (start + end) / 2;
            int middata = nums[mid];
            if (middata == k) {
            if (mid < length-1&&nums[mid+1] != k || mid == length-1)
                return mid;
            else start = mid + 1;            
            }
            else if(middata < k) start = mid+1;
            else end = mid-1;
           // cout << mid << endl;
            return Getlast(nums, start, k, end);
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla