Readme.md

丢失的练习册

by Xinran Fang

问题描述

开学了，阳光小学准备给每个学生发放三本练习册。为了方便发放，每本练习册上都印上了学生的学号。然而，运输过程中由于道路的颠簸，原本捆绑整齐的练习册散落一地，司机师傅再将练习册堆叠在一起时，学号已经完全打乱。更糟糕的是，当他清点练习册总数时，发现少了一本，为了尽快弄清楚丢失的是印有哪位学生学号的练习册，司机师傅只好拿出本子，一个个记录每个练习册上的学号。聪明的你能够通过编程的方法找到是印有哪个同学学号的练习册丢失了吗？

输入格式

第1行为学生的总数：N；

第2到第3N行为司机师傅记录的练习册上的学号；

注意：没有丢失练习册的学号会出现3次，而丢失练习册的学号只会出现2次。

输出格式

丢失练习册上对应的学号

输入样例

3
2021001  
2021001
2023002
2023003
2023002
2023003
2023002
2021001

输出样例

2023003

提示

1. 取值范围

N的取值范围为[1,1×106]的整数；

学生学号的取值范围为[0, 2×109]的整数；

2. 测试样例

1~3测试样例N<1×104;

4~5测试样例1×104<=N<=5×105；

6~10测试样例5×105<N<=1×106；

3. 时间和空间

本道OJ本身并不难，但对程序运行的时间和空间有较为严格的要求，时间需要为O(n)，空间为O(1)才能通过所有的测试样例，请同学们从算法效率的角度出发，选择合适的算法。