c - 未排序数组中元素的出现次数 O(n)

Question

这让我发疯:(

问题陈述:

输入未排序的数组。接下来，用户给出数字集合，程序应打印给定数字在该数组中的出现情况。

这应该以 O(n) 时间复杂度运行。

示例: 输入数组:[1, 1, 1, 2, 2, 0]

数字集合:

1

2

1

0

输出:

3

2

3

1

约束:数组的大小可以为 10^5，数字集合的大小可以为 10^5

P.S:我用 O(n^2) 编写了代码

#include<stdio.h>
#include<stdlib.h>
void main(){
    int *n,size,key,count=0;
    scanf("%d",&size);
    n=(int*)malloc(size*sizeof(int));
    for(int i=0;i<size;i++){
        scanf("%d",&n[i]);
    }
    scanf("%d",&key);
    for(int i=0;i<key;i++){
        count=0;
        int temp=0;
        scanf("%d",&temp);
        for(int j=0;j<size;j++){
            if(temp==n[j])
                 count+=1;
        }
        printf("\n");
        if(count==0){
            printf("NOT PRESENT");
        }
        else{
            printf("%d",count);
        }

    }

    }

欢迎任何帮助:)

Answer 1

元素的范围很小。因此，为可能的值创建一个计数器数组，并为找到的每个值增加计数。例如，如果找到 2，则递增 counter[2]。

然后给定您的数字集合，只需进行数组查找即可获得计数。