剑指offer——面试题38：数字在排序数组中出现的次数

剑指offer——面试题38：数字在排序数组中出现的次数

Solution1:复杂度为 O(n) $O(n)$的破算法。。。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int n = data.size();
        if(n == 0)
            return 0;
        else {
            int count = 0;
            for(int i = 0; i < n; i++) {
                if(data[i] == k)
                    count++;
            }
            return count;
        }
    }
};

Solution2:复杂度为 O(logn) $O(logn)$的二分查找算法。。
还顺手复习了下二分查找，挺好的。。。
递归版二分查找如下：

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int n = data.size();
        if(n == 0) 
            return 0;
        else {
            int lastnum = GetLastOfK(data, k, 0, n - 1), firstnum = GetFirstOfK(data, k, 0, n - 1);
            if(firstnum > -1 && lastnum > -1)
                return lastnum - firstnum + 1;
            else 
                return 0;
        }
    }

    int GetFirstOfK(vector<int> &data, int k, int begin, int end){
        if(begin > end)
            return -1;
        int middleindex = (begin + end) / 2;
        if(data[middleindex] == k) {
            if(middleindex > 0 && data[middleindex - 1] != k || middleindex == 0)
                return middleindex;
            else 
                end = middleindex - 1;
        }
         else if(data[middleindex] < k) {
            begin = middleindex + 1;
        }
        else if(data[middleindex] > k) {
            end = middleindex - 1;
        }
        return GetFirstOfK(data, k, begin, end);
    }

    int GetLastOfK(vector<int> &data, int k, int begin, int end){
        if(begin > end)
            return -1;
        int middleindex = (begin + end) / 2;
        if(data[middleindex] == k) {
            if(middleindex < data.size() - 1 && data[middleindex + 1] != k || middleindex == data.size() - 1)
                return middleindex;
            else 
                begin = middleindex + 1;
        }
         else if(data[middleindex] < k) {
            begin = middleindex + 1;
        }
        else if(data[middleindex] > k) {
            end = middleindex - 1;
        }
        return GetLastOfK(data, k, begin, end);
    }
};

Solution3:迭代版二分查找
以寻找last K为例说明迭代版二分查找的写法
参考网址：https://www.nowcoder.com/profile/7221411/codeBookDetail?submissionId=14533282

    private int getLastK(int [] array , int k, int start, int end){
        int length = array.length;
        int mid = (start + end) >> 1;
        while(start <= end){
            if(array[mid] > k){
                end = mid-1;
            }else if(array[mid] < k){
                start = mid+1;
            }else if(mid+1 < length && array[mid+1] == k){
                start = mid+1;
            }else{
                return mid;
            }
            mid = (start + end) >> 1;
        }
        return -1;
    }