我上学期期末考试的一道题:
小明正在开发一个校园活动签到系统。每次活动开始时，参与者通过扫描二维码签到，系统会实时记录每个参与者的ID号。但由于网络波动或误操作，部分参与者可能被重复提交。为了统计实际参与人数并生成准确的签到名单，小明需要对原始签到记录进行去重处理，并保留ID首次出现的顺序，以反映真实的签到先后。
请你帮助小明编写一个程序，从包含重复ID号的签到记录中提取出唯一的、按首次出现顺序排列的ID号序列。
输入格式:
第一行输入一个正整数 N（1≤N≤100），表示签到记录中包含的ID号数量。
第二行输入 N 个正整数（每个正整数不超过 100），代表签到的参与者的ID号，正整数之间用一个空格分隔。
输出格式:
输出一行，包含去重后的ID号序列，按首次出现的顺序排列，学号之间用一个空格分隔。行末不得有多余空格。
由于上个学期我学的是C语言，因此我先用C语言写：
方法1：双重暴力循环
代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
int main(){
int n;
scanf("%d",&n);
int *arr=(int*)malloc(n*sizeof(int));//申请一个足够大的空间
if(arr==NULL){
printf("空间申请失败！");//记得判空
return 1;
}
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);//初始化数组
}
for(int i=0;i<n;i++){
bool flag=1;//用他去标记是否出现重复
for(int j=0;j<i;j++){
if(arr[i]==arr[j]){
flag=0;//如果出现就位1
break;
}
}
if(flag==1){
printf("%d ",arr[i]);//输出不重复的元素
}
}
free(arr);//释放资源
return 0;
}
我朋友给了我一种更快的方法，毕竟双重暴力解是O(n^2)的暴力解法太慢了，下面是二分法，它是利用复制出来的数组排序二分和原数组标记比较，不过这个是多组数据的。
#include<stdio.h>
#include<stdlib.h>
// qsort 比较函数，用long long防int溢出
int cmp(const void* a, const void* b) {
long long x = *(int*)a;
long long y = *(int*)b;
return x > y ? 1 : (x < y ? -1 : 0);
}
// 二分查找：找目标元素第一次出现的下标,找不到返回-1，二分要求数组有序
int findFirst(int* sorted_arr, int n, int target) {
int left = 0, right = n – 1;
int res = -1;
while (left <= right) {
int mid = left + (right – left) / 2;
if (sorted_arr[mid] == target) {
res = mid;
right = mid – 1;
} else if (sorted_arr[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}
return res;
}
int main() {
int T;
// 先输入测试用例组数
if (scanf("%d", &T) != 1) return 0;
while (T–) {
int n;
if (scanf("%d", &n) != 1) return 0;
if (n == 0) {
printf("\\n");
continue;
}
int* arr = (int*)malloc(n * sizeof(int));
int* sorted_arr = (int*)malloc(n * sizeof(int));
int* isPrinted = (int*)calloc(n, sizeof(int)); // 自动初始化为0
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
sorted_arr[i] = arr[i];
}
qsort(sorted_arr, n, sizeof(int), cmp);
int first_print = 1;
for (int i = 0; i < n; i++) {
int num = arr[i];
int pos = findFirst(sorted_arr, n, num);
if (pos != -1 && !isPrinted[pos]) {
if (!first_print) {
printf(" ");
}
printf("%d", num);
first_print = 0;
isPrinted[pos] = 1;
}
}
// 每组数据输出完，强制换行，保证下一组在新行
printf("\\n");
free(arr);
free(sorted_arr);
free(isPrinted);
}
return 0;
}
这样写比暴力双循环解就快多了，几乎和双指针一样快了，不过能使用双指针前是要求要有序，那样会打乱原数组顺序，不合这道题的题意，下面是C语言双指针写法
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a,const void *b){
return *(int*)a-*(int*)b;
}
int main(){
int n;
scanf("%d",&n);
int *arr=(int*)malloc(n*sizeof(int));
if(arr==NULL){//记得判空
printf("申请空间失败！");
return 1;
}
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
qsort(arr,n,sizeof(int),compare);
int slow=0;
for(int fast=1;fast<n;fast++){
if(arr[fast]!=arr[slow]){//如果不相等，就让慢指针追上快指针，将快指针的值赋值给慢指针
slow++;
arr[slow]=arr[fast];
}//如果相等，就只让快指针向前移动，抛去重复元素，这里省去了一个fast++可写科不写，因为循环本来就会++。
}
for(int i=0;i<=slow;i++){//只输出慢指针所到的元素
printf("%d ",arr[i]);
}
free(arr);//释放资源
return 0;
}
C语言大概就这几种方法，如果有我不知道的，希望大佬们评论，当然还有哈希表法，但在后面的java和C++里，这种我更喜欢调库，不喜欢手写。
下面是java的解法，因为我写代码的时候都喜欢用流来输入输出，用PrintWriter一定要flush,不然不会有结果：
方法1：stream流（底部是hashcode方法），不直接用BufferedReader的原因是它一行只读一个数字和原输入不符合。
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
int n=Integer.parseInt(br.readLine().trim());
int []arr=new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.stream(arr).distinct().forEach(s->out.print(s+" "));//Lambada表达式
out.flush();
br.close();
out.close();
}
}
方法2：直接LinkedHashSet(可以保存原顺序）
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
int n=Integer.parseInt(br.readLine().trim());
int []arr=new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
LinkedHashSet<Integer> set=new LinkedHashSet<>();
for(int i=0;i<n;i++){
set.add(arr[i]);
}
set.stream().forEach(s->out.print(s+" "));
out.flush();
br.close();
out.close();
}
}
这两个代码本质上区别不大，都是哈希表的应用，时间复杂度大致相同。
其实可以用ArrayList的
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
int n=Integer.parseInt(br.readLine().trim());
int []arr=new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
ArrayList<Integer> list=new ArrayList<>();
for(int i=0;i<n;i++){
if(!list.contains(arr[i])){//里面没有我才加进去
list.add(arr[i]);
}
}
list.stream().forEach(s->out.print(s+" "));
out.flush();
br.close();
out.close();
}
}
还有一个我不常见的方法—位运算去重：用二进制去记录是否重复，不过long占64位，只能标记 0~63 的数字。
import java.io.*;
import java.util.*;
public class Main{
public static void main(String[] args)throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
PrintWriter out=new PrintWriter(System.out);
int n=Integer.parseInt(br.readLine().trim());
int []arr=new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0;i<n;i++){
arr[i] = Integer.parseInt(st.nextToken());
}
long flag=0;
for(int x: arr){
if((flag&(1<<x))==0){
// (1 << x) ：1左移x位，构造只有第x位为1的二进制数
// flag & (1 << x) ：按位与，判断flag的第x位是否为0
// 等于0说明该数字第一次出现，没有重复
out.print(x+" ");
flag|=1<<x;
//等于1标记已经出现过了
}
}
out.flush();
br.close();
out.close();
}
}
下面是C++的解法：
1.unique去重的原理是把相邻相同的元素只保留一个，其余都挪后面去，所以用之前都要排序的！把末尾的地址更新。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
int *arr=new int[n];
for (int i=0;i<n;i++) {
cin>>arr[i];
}
sort(arr,arr+n);//降序是sort(arr,arr+n,greater<int>())
int m = unique(arr, arr + n) – arr;
for (int i=0;i<m;i++) {
cout<<arr[i]<<" ";
}
delete []arr;
return 0;
}
2.set去重（相当于Java的TreeSet，会升序和去重，降序是set<int,greater<int>>，保留原顺序是unordered_set<int>)
#include <bits/stdc++.h>
using namespace std;
void print(int num) {
cout<<num<<" ";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
set<int> s;
int n;
cin>>n;
for (int i=0;i<n;i++) {
int num;
cin>>num;
s.insert(num);
}
for_each(s.begin(),s.end(),print);//自定义函数用for_each，其实也可以写仿函数
return 0;
}
仿函数：
class Print {
public:
// 重载 () 运算符
void operator()(int x) {
cout << x << " ";
}
};
3.还有哈希表（map（有序））,unordered_map（无序））
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
unordered_map<int,bool> map;//它的值bool类型来判断是否存在
int n;
cin>>n;
for (int i=0;i<n;i++) {
int num;
cin>>num;
map[num] = true;//用true保证他不重复，就是哈希表里已有的数字不能再进入
}
for (auto i:map) {
cout<<i.first<<" ";
}
return 0;
}
4.其实vector也可以去重：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie( nullptr);
vector<int> v;
int n;
cin>>n;
for (int i=0;i<n;i++) {
int num;
cin>>num;
if (find(v.begin(),v.end(),num)==v.end()) {//和Java的ArrayList一样，没在原有元素里找到，才加入，相当于去了重
v.push_back(num);
}
}
for (auto i:v) {
cout<<i<<" ";
}
return 0;
}
引用：洛谷P1469
题目描述
经过一段时间的紧张筹备，电脑小组的“RP 餐厅”终于开业了，这天，经理 LXC 接到了一个定餐大单，可把大家乐坏了！员工们齐心协力按要求准备好了套餐正准备派送时，突然碰到一个棘手的问题：筷子！
CX 小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成一双，更麻烦的是 CX 找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？
输入格式
第一行是一个整数，表示筷子的数量 n。
第二行有 n 个整数，第 i 个整数表示第 i 根筷子的长度 a_i。
输出格式
输出一行一个整数表示答案。
输入输出样例 #1
输入 #1
9
2 2 1 3 3 3 2 3 1
输出 #1
2
说明/提示
数据规模与约定
– 对于 30% 的数据，保证 n 小于等于pow(10,5)。
– 对于 100\\%的数据，保证 1≤n≤10 ^7+1，1≤a i ≤10 ^9。
提示
– 请注意数据读入对程序效率造成的影响。
– 请注意本题的空间限制为 8 Mb。
这是我一开始的写法，发现思路是对的，但这道题数据量极大，所以这样写是一定会超时的，数据大了哈希冲突嘛！这不是正解，且如果把哈希表改为一个计数器数组去写的话，其实虽然没有哈希冲突，但数据量过大就会栈溢出。
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
unordered_map<int,int> map;
for (int i=0;i<n;i++) {
map[arr[i]]++;
}
for (auto i:map) {
if (i.second%2==1) {
cout<<i.first<<" ";
break;
}
}
delete []arr;
return 0;
}
看了题解后，异或是最好可能也是唯一解，重要的是怎么理解它，我们知道x^x=0,x^0=x,就是异或本身就是0，异或0就是本身，所以交换a,b我们可以写：
a=a^b;
b=a^b;
a=a^b;
所以说我们让按时先为0，由异或的性质，我们可以交换的，如果一个元素x出现了偶数次，都和0异或后就是0，而如果奇数次出现最后它会是x^x^x…^x^0(省略号中有奇数个x)，当前面偶数个x异或运算完了后最后就是x^0=x(它本身），所以我们可以这样解这个题。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, x, ans = 0;
cin >> n;
while (cin >> x) {
ans ^= x;
}
cout << ans;
return 0;
}
总结一下，到现在我学了Java，C，C++语言，C语言-3个月，Java-3个月，C++-3个星期，说句实话，这几种语言有相通性，我总结常用去重方法不只是为了解题，其实我也可以看到语言的相通性，难的不是哪门语言，是算法，我老师这样说，去重也有时间上的快慢之分，在解题的时候找到合适的解法其实更重要，所以说在我们老师的启发下，类比着学习，就很有用了（至少我是这样认为的，并在类比中寻找差异），多总结，一个小问题也能有更广泛的深遂的思考的。
