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


参与人数:2597    时间限制:1秒   空间限制:32768K
本题知识点:  数组


题目描述

统计一个数字在已排序数组中出现的次数。

样例输入:
2 3 3 3 3 4 51
3

6,5,3,3,1,0
3

样例输出:
4
2


分析:
      数字在排序数组中出现的次数,首先想到的方法应该是用hash表,计算出数组中所有数据出现的次数,然后直接查找,时间复杂度O(n),空间复杂度O(n)。但这种方法未能利用该数组是已排序的特点,所以如果输入是已排好序的题目,要及时联想到二分查找。


具体步骤:先用二分法找到某个目标值k出现的位置,然后统计前面一半中k出现的次数sum1,后面一半中k出现的次数sum2,最后sum=sum1+1+sum2。二分查找时间复杂度是O(logn)。


AC代码:

#include<cstdio>
#include<vector>
using namespace std;
class Solution {
public:
    int GetNumberOfK(vector<int> data, int k) {
        int idx = biSearch(data,0, (int)data.size(), k);   // 某个k的位置为idx 
        if(idx == -1) return 0;  // 未找到 
        int sum = 1; // 如果能找到1个k,sum初始化为1 
        for(int j = idx - 1; j >= 0; j--){  // 统计之前的那个k所在位置idx的前面k出现的次数 
            if(data[j] == k) sum++;
            else break;
        }
        for(int j = idx + 1; j < (int)data.size(); j++){  // 统计之前的那个k所在位置idx的后面k出现的次数
            if(data[j] == k) sum++;
            else break;
        }
        return sum;
    }     
    int biSearch(vector<int> &data, int begin, int end, int k){
        if(begin >= end) return -1;
        int mid = (begin + end)/2;
        if(data[mid] == k) return mid;  // 如果在区间mid处找到,提前返回;否则递归地在前一半去找,否则在后一半去找,总能找到 
        int pos1, pos2 = -1;
        pos1 = biSearch(data,begin,mid,k); 
        if(pos1 != -1) return pos1;
        pos2 = biSearch(data,mid + 1, end,k); 
        if(pos2 != -1) return pos2;              
        return -1;
    }
};
// 以下为测试 
int main()
{
	Solution sol;
	vector<int> vec1={1,3,4,5};
	vector<int> vec2={6,5,3,3,1,0};	
	int res1 = sol.GetNumberOfK(vec1, 4);
	int res2 = sol.GetNumberOfK(vec2, 3);	
	printf("%d\n", res1);	
	printf("%d\n", res2);		
	return 0;
}