题目描述

• 统计一个数字在排序数组中出现的次数
• 例如，输入排序数组 {1，2，3，3，3，3，4，5} 和数字 3，由于 3 在这个数组中出现了 4 次，因此输出 4

题目解读

• 剑指Offer 264

代码

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int GetFirstOfK(vector<int>& data, int left, int right, int k){
        if(left <= right){
            int index = (left + right) >> 1;
            int mid = data[index];

            if(k < mid){
                right = index-1;
            }
            else if(k > mid){
                left = index+1;
            }
            else{ // k == mid

                if((index == 0) || (index > 0 && data[index-1] != k)){
                    return index;
                }
                else{
                    right = index-1;
                }
            }
            return GetFirstOfK(data, left, right, k);

        }
        else{
            return -1;
        }
    }

    int GetLastOfK(vector<int>& data, int length, int left, int right, int k){
        if(left <= right){
            int index = (left + right) >> 1;
            int mid = data[index];

            if(k < mid){
                right = index-1;
            }
            else if(k > mid){
                left = index+1;
            }
            else{ // k == mid

                if((index == length) || (index < length && data[index+1] != k)){
                    return index;
                }
                else{
                    left = index+1;
                }
            }
            return GetLastOfK(data, length, left, right, k);

        }
        else{
            return -1;
        }
    }

    int GetNumberOfK(vector<int> data ,int k) {
        int length = data.size();
        if(length == 0){
            return 0;
        }

        int first = GetFirstOfK(data, 0, length-1, k);
        int last  = GetLastOfK(data, length-1, 0, length-1, k);

        if(first != -1 && last != -1){
            return last - first + 1;
        }
        return 0;
    }
};


int main(){
    Solution ss;
    int a[10] = {1, 2, 3, 3, 3, 3, 4, 5};
    vector<int> data;
    for(int i=0; i < 8; i++){
        data.push_back(a[i]);
    }
    cout<<ss.GetNumberOfK(data, 3);
}

总结展望

• 二分查找的经典应用.