题解 | #顺时针旋转矩阵#

方法一：

• 暴力，从头开始找到第一个值为k的元素，再计算连续的k的个数即可。缺点：没有利用好有序数组的特性。

代码如下：

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int ans;
        for(int i=0;i<data.size();i++){
            if(data[i]==k){
                int j=i+1;
                //从第一个为k的元素起，找到第一个不为k的元素止。
                while(j<data.size()&&data[j]==k)
                    j++;
                return j-i;
            }
        }
        return 0;
    }
};

复杂度分析：

时间复杂度：O(n)，最坏情况，k在数组末尾，需要n次for循环。
空间复杂度：O(1)，常数个临时变量。

方法二：

• 利用数组有序的特征，考虑使用二分法。
• 二分法找到值为k的元素，然后再寻找附近连续的k的个数。

图解如下：

代码如下：

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int ans;
        int left=0,right=data.size()-1,mid;
        while(left<=right){
            //二分法寻找等于k的值。
            mid=(left+right)/2;
            if(data[mid]<k){
                left=mid+1;
            }
            else if(data[mid]>k){
                right=mid-1;
            }
            else{
                //找到mid附近值都等于k的数目。
                int i=mid-1,j=mid+1;
                //此处的while循环的判断条件也可以是i>=left，j<=right，不过执行起来两者并没有区别。
                while(i>=0&&data[i]==k)
                    i--;
                while(j<=data.size()-1&&data[j]==k)
                    j++;
                return j-i-1;
            }
        }
        return 0;
    }
};

复杂度分析：

时间复杂度：O(n)，二分法找到等于k的数是O(logn)，还受到k的数量的影响，最坏情况下全部为k则需要O(n)。
空间复杂度：O(1)，常数个临时变量。