我的描述
时间紧迫,不说了。
题目描述
给个数组,找出重复数。
例如:2 4 2 这三个数中,2重复了,所以输出是二,注意,在
多个数重复时,输出任意一个就可以了。
样例
输入样例1:
3
2 4 3
输出样例1:
-1
输入样例2:
6
3 5 6 2 3 2
输出样例2:
2
输入样例3:
2
9999 9999
输出样例3:
9999
(注:样例2的输出也可以为3。)
算法1
(桶排序)
桶排序就是好多个桶,有一个就加加。例如样例2:
3 5 6 2 3 2
0 1 2 3 4 5 6
第一个数:3 0 0 0 1 0 0 0
第二个数:5 0 0 0 1 0 1 0
第三个数:6 0 0 0 1 0 1 1
第四个数:2 0 0 1 1 0 1 1
第五个数:3 0 0 1 2 0 1 1
第六个数:2 0 0 2 2 0 1 1
最终可得出2和3出现两次,是最多的。
C++ 代码
#include<iostream>
using namespace std;
int n,a,sum[10000];//没给范围,先设一万吧。
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;//随输随做,不需要数组。
sum[a]++;//桶累计。
}
int maxx=0,j;
for(int i=1;i<=10000;i++){
if(2<=sum[i]){
cout<<i<<endl;
return 0;
}
}
cout<<"-1"<<endl;
return 0;
}
算法2
(sort)
桶排序虽然好理解,但浪费空间。例如样例3:
9999 9999
0 1 2 3 4 5 6 …… 9998 9999
第一个数:3 0 0 0 0 0 0 0 …… 0 1
第二个数:5 0 0 0 0 0 0 0 …… 0 2
有点费空间😅。
所以用sort可以解决这个问题。
9999 9999 sort排序一下为 9999 9999 前后重复,所以重复,完美。
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[10000];//还是没给范围,先设一万吧。
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
if(a[i]==a[i+1]){//有重的
cout<<a[i]<<endl;
return 0;
}
}
cout<<"-1"<<endl;
return 0;
}
总结!
点一下这个再走呗下☟