信息学奥赛一本通1117：整数去重 视频题解

信息学奥赛一本通 1117：整数去重 视频题解

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 26883 通过数: 15361
【题目描述】
给定含有n个整数的序列，要求对这个序列进行去重操作。所谓去重，是指对这个序列中每个重复出现的数，只保留该数第一次出现的位置，删除其余位置。

【输入】
输入包含两行：

第一行包含一个正整数n（1≤n≤20000），表示第二行序列中数字的个数；

第二行包含n个整数，整数之间以一个空格分开。每个整数大于等于10、小于等于5000。

【输出】
输出只有一行，按照输入的顺序输出其中不重复的数字，整数之间用一个空格分开。

【输入样例】
5
10 12 93 12 75
【输出样例】
10 12 93 75

书上范例：

通用思维算法：

#include<bits/stdc++.h>
using namespace std;
//微信请加 14808098 一起快乐学习信息学奥赛
int a[20005];
int n;
bool b[20005];
int main() {cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}	/*19999+19998+19997+...+0;= （首项+末项）*项数/2= (19999+0)*20000/2= 4亿*/int  ans = 0;for(int i=1;i<=n;i++){for(int j=1;j<i;j++){ans++;if(a[j]==a[i]){b[i] = 1;break;}} }for(int i=1;i<=n;i++){if(b[i]!=1){printf("%d ",a[i]);}}return 0;
}
/*
5
10 12 93 12 75 12a[0]=10 a[1]=12 a[2]=93 a[3]=12 a[4]=75 a[5]=12
b[0]=0 b[1]=0  b[2]=0  b[3]=1    b[4]= 0  b[5]=1a[0]=10 a[1]=12 a[2]=93 a[4]=75*/

优化算法：

#include<bits/stdc++.h>
using namespace std;
//微信请加 14808098 一起快乐学习信息学奥赛
int a[20005];
bool b[20005];
int n; 
bool c[5005]; // 
int main() {cin>>n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);}for(int i=1;i<=n;i++){int x = a[i];if(c[x]==0){c[x] = 1;}else{b[i] = 1;}}for(int i=1;i<=n;i++){if(b[i]!=1){printf("%d ",a[i]);}}return 0;
}
/*
a[0]=10 a[1]=12 a[2]=93 a[3]=12 a[4]=75 a[5]=12
b[0]=0 b[1]=0  b[2]=0  b[3]=1    b[4]= 0  b[5]=1
c[10]=1 c[12]=1 c[93]=1 c[12]=1 c[75]=1 c[5]=1
*/