数组中的频度
Time Limit:4000MS Memory Limit:30000KB
Description
设A[1..n] 是一个由n 个整数组成的数组，x 是一个整数，给出一个分治算法，要求找出 x 在数组 A 中的频度，即 x 在A 中出现的次数。
Input
输入的第一行为两个正整数，n(0<=n<=100000)和m(0<m<50000)，n表示数组A有几个元素，m表示需要查找的x的个数。
接下去的n行，每行一个整数，范围为0到2^31,表示数组A中的元素Ai
再接下去的m行，每行一个整数mi(0<=mi<=2^31)，表示你要查找mi在数组A出现的次数
(提示：对于大规模的输入，请使用scanf而不是cin)
Output
输行为m行，每行一个整数，表示对于每一个mi，输出mi在数组A中出现的次数。
Sample Input
5 2
1
2
3
1
5
1
4
Sample Output
2
0
快速排序，然后二分查找
1
#include <stdio.h>
2
3#define L 100009
4
5int n, m, a[ L ], cnt[ L ];
6
7
void sort( int h, int t ) 
{
8
int i, j, x;
9
if ( h >= t ) {
10 return;
11
}
12 i = h;
13 j = t;
14 x = a[ h ];
15 while ( i < j ) {
16 while ( (i<j) && (x<=a[j]) ) {
17 --j;
18 }
19 if ( i < j ) {
20 a[ i++ ] = a[ j ];
21 }
22 while ( (i<j) && (a[i]<=x) ) {
23 ++i;
24 }
25 if ( i < j ) {
26 a[ j-- ] = a[ i ];
27 }
28 }
29 a[ i ] = x;
30 sort( h, i - 1 );
31 sort( i + 1, t );
32
}
33
34void init() {
35 int i, t;
36 sort( 0, n-1 );
37 t = 1;
38 cnt[ 0 ] = 1;
39 for ( i = 1; i < n; ++i ) {
40 if ( a[ i ] == a[ i - 1 ] ) {
41 ++cnt[ t-1 ];
42 }
43 else {
44 a[ t ] = a[ i ];
45 cnt[ t++ ] = 1;
46 }
47 }
48 n = t;
49}
50
51int query( int x ) {
52 int low = 0, high = n-1, mid;
53 while ( low <= high ) {
54 mid = ( low + high ) / 2;
55 if ( x < a[ mid ] ) {
56 high = mid - 1;
57 }
58 else if ( a[ mid ] < x ) {
59 low = mid + 1;
60 }
61 else {
62 return cnt[ mid ];
63 }
64 }
65 return 0;
66}
67
68int main() {
69 int i, x;
70 scanf( "%d%d", &n, &m );
71 for ( i = 0; i < n; ++i ) {
72 scanf( "%d", a+i );
73 }
74 init();
75 while ( m-- > 0 ) {
76 scanf( "%d", &x );
77 printf( "%d\n", query(x) );
78 }
79 return 0;
80}
81