一、我们首先引出最基础的一道题目：

 一段序列中，有一个数只出现了一次，其余数都出现了两次，找出这个出现一次的数并输出：

在这里一般我们会有三种解法：

①用一个vis数组标记，记录每一个数出现的次数，遍历一遍找出一次的数即可。

    scanf("%lld",&n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%lld",&num[i]);
        vis[num[i]]++;
    }

为了优化时间复杂度的话我们遍历vis数组时我们只需要找到第一个为1的数即可。但是如果这个特殊数时1e8的话会出现两个问题，第一个问题：1e8的标记数组是内存极限了，导致该题目无法继续开数组了。

第二个问题：时间复杂度也是 1e8 因为你需要找到为1的数。

②为了缓解上述问题带来的不足，我们还有下一种办法：

1)：我们将数组排序，如果这个数只出现了一次，那么它两边的数绝对不和他相等：

例如：S={4，4，1，5，5}，排序完之后产生{1，4，4，5，5} 只有1既不和它左边的数相等也不和他右边的数相等，在这里我们需要默认数组从1开始，然后将 a[0]，a[n+1] 赋值为一个序列中不可能出现的数，就可以解决如果这个数在 第一个或者在最后一个的情况。

2)：这里我们还可以推广到 有 多个 出现一次的数 ：

例如两个：S={1,1,4,5,2,3,3}  排序完后产生 {1,1,2,3,3,4,5} 我们发现只有2，4，5既不等于左边的数，也不等于右边的数所以，出现一次的数应该为 2，4，5.

    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    sort(num+1,num+1+n);
    num[0]=INF;num[n]=INF;//INF赋值为最大值
    for(int i=1;i<=n;i++)
    {
        if(num[i]!=num[i-1]&&num[i]!=num[i+1])
        {
            res[++cnt]=num[i];
            if(cnt==k) break;//k是 题目中给出 几个数出现了一次，或者没有给出的话去掉这个条件就可以统计出有多少数字只出现了一次
        }
    }

3)：复杂度：排序复杂度+n(比较稳定，如果n为1e6，2sec之内可以过)

③第二种方法，虽然简单但是还是不够优，我们来看一下最优解：

1):理解一种位运算 ：异或 (符号^)：当两个数字进行异或时，把它们拆成2进制表示，如果 两数 相同 则该位为0，不相同则为1

例如，3二进制：（011） || 4二进制 ：（1 0 0） 3与4 异或的结果就是 : 1 1 1 (每位都不一样)

2)：根据异或的性质，得到：

如果两个相同的数进行异或的话，那么这个数为0&&0异或任何数都是它本身

所以我们根据这个性质，可以对数组里的每一个数异或一遍，那么所有相等的数就成了0，0再一步异或现在的特殊数，答案就是我们要求的特殊数。

3)：注意这种做法只适用于一个特殊数的时候，如果两个下面会讲。

代码：

ll n,m;
ll num[maxn];
ll cal()
{
    ll sum=0;//初始设为0，0异或任何数为本身
    for(int i=1;i<=n;i++)
        sum^=num[i];
    return sum;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    m=cal();
    printf("%lld\n",m);
    return 0;
}

二、再引出一道稍微增加难度的题目

一段序列中，有一个数出现了1次，其余的数出现了3次，求出这个特殊数。

①同上述第一种做法，遍历vis数组

②同上述第二种做法，只要出现一次排序后绝对满足规律

③下面看一下，位运算的操作：

1)：首先想还可以不可以进行异或？不可以！多出了一个数,最后答案一定是我们想要的结果了！

2)：那么怎么处理的，举一个例子 S={1,1,1,2,3,3,3}  ，位运算绝对和二进制有关我们以某种形式列一下二进制：

0 0 1

0 0 1

0 0 1

0 1 0

0 1 1

0 1 1

0 1 1

0 4 6

列二进制为什么会出现4，6？这里4，6表示的是：二进制的第几位 1 出现的 个数。所以到这里你应该恍然大悟了吧。

如果在该位 1 的次数 不是 3的倍数 因为出现了三次，多余的那一次绝对是 特殊数 的1，所以我们只需要表示一下特殊数就可以了，例如上述 特殊数的二进制就是 (0 1 0) 即2。

同样该方法可以推广到 其余数 出现k次，特殊数出现一次的情况，判断条件是 bit[i]%k!=0。

3) 算法理解了之后，程序的简化也很关键，这里用左移与右移加位运算处理：

ll n,m;
ll num[maxn];
ll cal()
{
    ll sum=0;
    int bit[35];memset(bit,0,sizeof(bit));
    for(int i=1;i<=n;i++)
        for(int k=0;k<32;k++)
            if((num[i]>>k)&1)//判断该数 第 k位 是否为1
                bit[k]+=1;
    for(int i=0;i<32;i++)
        if(bit[i]%3!=0)
            sum|=(1<<i);//用位运算加权值
    return sum;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    m=cal();
    printf("%lld\n",m);
    return 0;
}

三、最后看一个难一点的题目

一个序列中，有两个特殊数出现了一次，其余数出现两次，求出这两个特殊数.

①同样，完全可以，vis找到两个之后推出

②同样，完全可以，k个数都可以

③位运算实现：

1)：我们考虑是否可以异或，异或最后结果为 两个特殊数 的异或 ，所以不可取。

2)：我们想 是否 可以把 这两个 特殊数分开，分到不同的组里就可以 异或分别求出这两个数了。

3)：根据1我们可以得到 最终的数 是两个数 的异或，那么既然是两个数的异或 只要这两个数不相等 一定会出现1，1代表着在该位 这两个数是不一样的，所以我们 可以 按照这个把两个数分开：

把该位出现0的放到一组中

把该位出现1的放到一组中，最后分别异或得到两个数，即为我们的答案。

PS：如果1中异或结果有多个1，我们只取最前面的那位作为区分就可以了。另外我们可以保证 分到 每一组里的 绝对都是以 k个出现2次的 和 1个出现 一次的数组成。

所以代码实现：

#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define MIN(x,y) ((x)<(y)?(x) : (y))
#define MAX(x,y) ((x)>(y)?(x) : (y))
#define PI 3.1415926535
#include <set>
#include <sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=1e12;

const int maxn=1e8+5;

const ll mod=998244353;
const double eps=1e-30;
ll n,m;
ll num[maxn];
void cal()
{
    ll vis=0;int z;
    ll num1=0,num2=0;
    for(int i=1;i<=n;i++) vis^=num[i];
    for(int i=0;i<32;i++)
        if(((vis>>i)&1))
        {
            z=i;//找到第一个位为1的位置
            break;
        }
    for(int i=1;i<=n;i++)
    {
        if(((num[i]>>z)&1)) num1^=num[i];
        else num2^=num[i];
    }
    printf("%lld %lld\n",num1,num2);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
    cal();
    return 0;
}

最近这几天不想写代码，有点心累，但是还是需要坚持啊，为了梦想加油！你也是 my reader