数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。
解法:由于数组是有序的,可以采用二分查找的思想,分别查找连续k值得左边界和有边界,
class Solution {
public:
    int GetStartOfK(vector<int> data, int k){  // 查找左边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size()-1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] >= k)        // 大于等于k时,end向start紧靠,找到左边界
                end = mid - 1;
            else
                start = mid + 1;
        }
        if(data[start] == k)
            return start;
        else
            return -1;
    }
    int GetEndOfK(vector<int> data, int k){  //查找右边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size() - 1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] <= k)         // 小于等于k时, start向end紧靠,找到右边界
                start = mid + 1;
            else
                end = mid - 1;
        }
        if(data[end] == k)
            return end;
        else
            return -1;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        if(data.size() > 0){
            int start = GetStartOfK(data, k);
            int end = GetEndOfK(data, k);
            if(start > -1 && end > -1)
                count = end - start + 1;
        }
        return count;
    }
};

 

Leave a Reply

Your email address will not be published. Required fields are marked *