面试题38

题目描述：

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

输入：

每个测试案例包括两行：

第一行有1个整数n，表示数组的大小。1<=n <= 10^6。

第二行有n个整数，表示数组元素，每个元素均为int。

第三行有1个整数m，表示接下来有m次查询。1<=m<=10^3。

下面有m行，每行有一个整数k，表示要查询的数。

输出：

对应每个测试案例，有m行输出，每行1整数，表示数组中该数字出现的次数。

样例输入：

8 1 2 3 3 3 3 4 5 1 3

样例输出：

4

第一眼做法：从头扫到尾。统计各个数据出现的次数，时间复杂度为O（n*m），显然会TLE；

正解：二分查找。如果直接使用二分查找去做的话，最坏的情况查找的时间复杂度仍然为O（n),同样会TLE。

但我们可以采用二分查找的思想去做，即找到区间k的首位第一次出现的位置。然后就可以求解了。这样可以时间复杂度为O（n*logn*m）

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;

const int MAX = 1000005;
int num[MAX];

int Deal1( int *num, int l, int r, int k, int len ){
	if( l > r )
		return -1;
	int mid = (l + r) / 2;
	if (num[mid] == k){
		if ((mid - 1 >= 0 && num[mid - 1] != k) ?? mid == 0){
			return mid;
		}
		else{
			r = mid - 1;
		}
	}
	else if (num[mid] > k){
		r = mid - 1;
	}
	else{
		l = mid + 1;
	}
	Deal1(num, l, r, k, len);
}

int Deal2( int *num, int l, int r, int k, int len ){
	if( l > r )
		return -1;
	int mid = (l + r) / 2;
	if (num[mid] == k){
		if ((mid + 1 <= len - 1 && num[mid + 1] != k) ?? mid == len - 1){
			return mid;
		}
		else{
			l = mid + 1;
		}
	}
	else if (num[mid] > k){
		r = mid - 1;
	}
	else
		l = mid + 1;
	Deal2(num, l, r, k, len);
}

int GetOrder(int *num, int l, int r, int k, int n ){
	int ans = 0;
	if (num != NULL && n > 0){
		int First = Deal1( num, 0, n - 1, k, n );
		int Last = Deal2( num, 0, n - 1, k, n );
		if (First != -1 && Last != -1){
			ans = Last - First + 1;
		}
	}
	return ans;
}

int main(){
	int n, m, k;
	while(scanf( "%d", &n ) != EOF ){
		for (int i = 0; i < n; ++i){
			//cin >> num[i];
                         scanf( "%d", &num[ i ] );
		}
		scanf( "%d", &m );//cin >> m;
		while (m--){
			scanf( "%d", &k );//in >> k;
			int ans = GetOrder( num, 0, n, k, n );
			//cout << ans << endl;
		       printf( "%d\n", ans );
}
	}
	return 0;
}