gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-02 09:17:53 25 4
gpt4 key购买 nike

这让我发疯:(

问题陈述:

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

这应该以 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);
}

}

}

欢迎任何帮助:)

最佳答案

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

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

关于c - 未排序数组中元素的出现次数 O(n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45196515/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com