coreBugZJ

此 blog 已弃。

数组中的频度——算法作业 2.1,EOJ 1049

数组中的频度

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 
 7void 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

posted on 2011-03-28 19:34 coreBugZJ 阅读(476) 评论(2)  编辑 收藏 引用 所属分类: 课内作业

Feedback

# re: 数组中的频度——算法作业 2.1,EOJ 1049 2011-04-08 22:23 老头颜

厉害!!!牛叉!!  回复  更多评论   

# re: 数组中的频度——算法作业 2.1,EOJ 1049 2011-04-08 22:24 老头颜

@老头颜
学习之  回复  更多评论   



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理