我上学期期末考试的一道题:小明正在开发一个校园活动签到系统。每次活动开始时参与者通过扫描二维码签到系统会实时记录每个参与者的ID号。但由于网络波动或误操作部分参与者可能被重复提交。为了统计实际参与人数并生成准确的签到名单小明需要对原始签到记录进行去重处理并保留ID首次出现的顺序以反映真实的签到先后。请你帮助小明编写一个程序从包含重复ID号的签到记录中提取出唯一的、按首次出现顺序排列的ID号序列。输入格式:第一行输入一个正整数 N1≤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(arrNULL){ printf(空间申请失败);//记得判空 return 1; } for(int i0;in;i){ scanf(%d,arr[i]);//初始化数组 } for(int i0;in;i){ bool flag1;//用他去标记是否出现重复 for(int j0;ji;j){ if(arr[i]arr[j]){ flag0;//如果出现就位1 break; } } if(flag1){ printf(%d ,arr[i]);//输出不重复的元素 } } free(arr);//释放资源 return 0; }我朋友给了我一种更快的方法毕竟双重暴力解是O(n^2)的暴力解法太慢了下面是二分法它是利用复制出来的数组排序二分和原数组标记比较不过这个是多组数据的。#includestdio.h #includestdlib.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(arrNULL){//记得判空 printf(申请空间失败); return 1; } for(int i0;in;i){ scanf(%d,arr[i]); } qsort(arr,n,sizeof(int),compare); int slow0; for(int fast1;fastn;fast){ if(arr[fast]!arr[slow]){//如果不相等就让慢指针追上快指针将快指针的值赋值给慢指针 slow; arr[slow]arr[fast]; }//如果相等就只让快指针向前移动抛去重复元素这里省去了一个fast可写科不写因为循环本来就会。 } for(int i0;islow;i){//只输出慢指针所到的元素 printf(%d ,arr[i]); } free(arr);//释放资源 return 0; }C语言大概就这几种方法如果有我不知道的希望大佬们评论当然还有哈希表法但在后面的java和C里这种我更喜欢调库不喜欢手写。下面是java的解法因为我写代码的时候都喜欢用流来输入输出用PrintWriter一定要flush,不然不会有结果方法1stream流底部是hashcode方法不直接用BufferedReader的原因是它一行只读一个数字和原输入不符合。import java.io.*; import java.util.*; public class Main{ public static void main(String[] args)throws IOException{ BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); PrintWriter outnew PrintWriter(System.out); int nInteger.parseInt(br.readLine().trim()); int []arrnew int[n]; StringTokenizer st new StringTokenizer(br.readLine()); for(int i0;in;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 brnew BufferedReader(new InputStreamReader(System.in)); PrintWriter outnew PrintWriter(System.out); int nInteger.parseInt(br.readLine().trim()); int []arrnew int[n]; StringTokenizer st new StringTokenizer(br.readLine()); for(int i0;in;i){ arr[i] Integer.parseInt(st.nextToken()); } LinkedHashSetInteger setnew LinkedHashSet(); for(int i0;in;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 brnew BufferedReader(new InputStreamReader(System.in)); PrintWriter outnew PrintWriter(System.out); int nInteger.parseInt(br.readLine().trim()); int []arrnew int[n]; StringTokenizer st new StringTokenizer(br.readLine()); for(int i0;in;i){ arr[i] Integer.parseInt(st.nextToken()); } ArrayListInteger listnew ArrayList(); for(int i0;in;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 brnew BufferedReader(new InputStreamReader(System.in)); PrintWriter outnew PrintWriter(System.out); int nInteger.parseInt(br.readLine().trim()); int []arrnew int[n]; StringTokenizer st new StringTokenizer(br.readLine()); for(int i0;in;i){ arr[i] Integer.parseInt(st.nextToken()); } long flag0; for(int x: arr){ if((flag(1x))0){ // (1 x) 1左移x位构造只有第x位为1的二进制数 // flag (1 x) 按位与判断flag的第x位是否为0 // 等于0说明该数字第一次出现没有重复 out.print(x ); flag|1x; //等于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; cinn; int *arrnew int[n]; for (int i0;in;i) { cinarr[i]; } sort(arr,arrn);//降序是sort(arr,arrn,greaterint()) int m unique(arr, arr n) - arr; for (int i0;im;i) { coutarr[i] ; } delete []arr; return 0; }2.set去重相当于Java的TreeSet会升序和去重降序是setint,greaterint保留原顺序是unordered_setint)#include bits/stdc.h using namespace std; void print(int num) { coutnum ; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); setint s; int n; cinn; for (int i0;in;i) { int num; cinnum; 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_mapint,bool map;//它的值bool类型来判断是否存在 int n; cinn; for (int i0;in;i) { int num; cinnum; map[num] true;//用true保证他不重复就是哈希表里已有的数字不能再进入 } for (auto i:map) { couti.first ; } return 0; }4.其实vector也可以去重#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie( nullptr); vectorint v; int n; cinn; for (int i0;in;i) { int num; cinnum; if (find(v.begin(),v.end(),num)v.end()) {//和Java的ArrayList一样没在原有元素里找到才加入相当于去了重 v.push_back(num); } } for (auto i:v) { couti ; } return 0; }引用洛谷P1469题目描述经过一段时间的紧张筹备电脑小组的“RP 餐厅”终于开业了这天经理 LXC 接到了一个定餐大单可把大家乐坏了员工们齐心协力按要求准备好了套餐正准备派送时突然碰到一个棘手的问题筷子CX 小朋友找出了餐厅中所有的筷子但遗憾的是这些筷子长短不一而我们都知道筷子需要长度一样的才能组成一双更麻烦的是 CX 找出来的这些筷子数量为奇数但是巧合的是这些筷子中只有一只筷子是落单的其余都成双善良的你可以帮 CX 找出这只落单的筷子的长度吗输入格式第一行是一个整数表示筷子的数量 n。第二行有 n 个整数第 i 个整数表示第 i 根筷子的长度 a_i。输出格式输出一行一个整数表示答案。输入输出样例 #1输入 #192 2 1 3 3 3 2 3 1输出 #12说明/提示数据规模与约定- 对于 30% 的数据保证 n 小于等于pow(10,5)。- 对于 100\%的数据保证 1≤n≤10 ^711≤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; cinn; int *arrnew int[n]; for(int i0;in;i){ cinarr[i]; } unordered_mapint,int map; for (int i0;in;i) { map[arr[i]]; } for (auto i:map) { if (i.second%21) { couti.first ; break; } } delete []arr; return 0; }看了题解后异或是最好可能也是唯一解重要的是怎么理解它我们知道x^x0,x^0x,就是异或本身就是0异或0就是本身所以交换a,b我们可以写aa^b;ba^b;aa^b;所以说我们让按时先为0由异或的性质我们可以交换的如果一个元素x出现了偶数次都和0异或后就是0而如果奇数次出现最后它会是x^x^x...^x^0(省略号中有奇数个x)当前面偶数个x异或运算完了后最后就是x^0x(它本身所以我们可以这样解这个题。#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; }总结一下到现在我学了JavaCC语言C语言-3个月Java-3个月C-3个星期说句实话这几种语言有相通性我总结常用去重方法不只是为了解题其实我也可以看到语言的相通性难的不是哪门语言是算法我老师这样说去重也有时间上的快慢之分在解题的时候找到合适的解法其实更重要所以说在我们老师的启发下类比着学习就很有用了至少我是这样认为的并在类比中寻找差异多总结一个小问题也能有更广泛的深遂的思考的。