數(shù)組中的頻度
Time Limit:4000MS Memory Limit:30000KB
Description
設(shè)A[1..n] 是一個(gè)由n 個(gè)整數(shù)組成的數(shù)組，x 是一個(gè)整數(shù)，給出一個(gè)分治算法，要求找出 x 在數(shù)組 A 中的頻度，即 x 在A 中出現(xiàn)的次數(shù)。
Input
輸入的第一行為兩個(gè)正整數(shù)，n(0<=n<=100000)和m(0<m<50000)，n表示數(shù)組A有幾個(gè)元素，m表示需要查找的x的個(gè)數(shù)。
接下去的n行，每行一個(gè)整數(shù)，范圍為0到2^31,表示數(shù)組A中的元素Ai
再接下去的m行，每行一個(gè)整數(shù)mi(0<=mi<=2^31)，表示你要查找mi在數(shù)組A出現(xiàn)的次數(shù)
(提示：對于大規(guī)模的輸入，請使用scanf而不是cin)
Output
輸行為m行，每行一個(gè)整數(shù)，表示對于每一個(gè)mi，輸出mi在數(shù)組A中出現(xiàn)的次數(shù)。
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