剑指 Offer——数字在排序数组中出现的次数

1. 题目

2. 解答

时间复杂度为 $O (n)$ 的算法，顺序遍历数组，当该数字第一次出现时开始记录次数。

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

时间复杂度为 $O (l o g n)$ 的算法，借助二分查找，分别查找该数字第一次在数组中出现的位置和最后一次在数组中出现的位置，然后即可得到出现的次数。

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        
        int n = data.size();
        if (n == 0)    return 0;
        int num = 0;
        
        int i = Find_First_K(data, k);
        int j = Find_Last_K(data, k);
        num = (i == -1) ? 0 : (j - i + 1);
        
        return num;
    }
    
    int Find_First_K(vector<int> &data, int k)
    {
        int left = 0;
        int right = data.size() - 1;
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (data[mid] == k)
            {
                // 到数组头了或者前一个元素不为 k
                if (mid == 0 || data[mid-1] != k)    return mid;
                else    right = mid - 1;
            }
            else if (data[mid] > k)    right = mid - 1;
            else    left = mid + 1;
        }
        
        return -1;
    }
    
    int Find_Last_K(vector<int> &data, int k)
    {
        int left = 0;
        int right = data.size() - 1;
        
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (data[mid] == k)
            {
                // 到数组尾了或者后一个元素不为 k
                if (mid == data.size() - 1 || data[mid+1] != k)    return mid;
                else    left = mid + 1;
            }
            else if (data[mid] > k)    right = mid - 1;
            else    left = mid + 1;
        }
        
        return -1;
    }
};

获取更多精彩，请关注「seniusen」!