#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <iostream>
#include<vector>
#include<string>
#include<set>
#include<unordered_set>
#include<queue>
#include<map>
using namespace std;
//1。 找出1个出现1个次的数
/*
思路就是用异或，异或的作用能够将bit位相同的1,1 0,0变成0
这正好与偶数的思路相应。把所有数异或起来，就会发现，只出现1次的数上面的1的bit位才会被保存。
*/
int findone(int a[],int n)
{
int ans = 0;
for (int i = 0; i < n; i++)
{
ans ^= a[i];
}
return ans;
}
//2。找出两个出现1次的数
/*
出现两个1次的数再用1的方法就不起效了，但是有1种办法，就是把全部数组分成两部份。
每部份包括1个数，这样就能够转换为求出现1次数的方法。
如何分解呢，首先需要找出这两个数的区分：
a: 0 0 1 1
b: 0 1 0 1
异或:0 1 1 0
我们会发现a和b的比特位异或，有4种情况，其中两种情况结果是1.当结果比特位异或等于1的时候，a和b的比特位肯定不同。
这就是区分，我们可以通过找某1位比特位是不是为1来辨别成2个组。
*/
int findbit1(int n)
{//找出低位开始第1个为1的比特位,其他清0
return n&~(n - 1); // n&-n也能够
}
void findtwo(int a[],int n)
{
int ans1 = 0, ans2 = 0;
int flag = findone(a, n); //全部异或，结果=a^b 其他变成0;
flag = findbit1(flag);
for (int i = 0; i < n; i++)
{
if (a[i] & flag)
ans1 ^= a[i];
else
ans2 ^= a[i];
}
cout << ans1 << endl;
cout << ans2 << endl;
}
//3。找出3个出现1次的数
/*
这次更加困难了，由于没法直接划分成2组。 比如a,b,c
a 0 0 0 0 1 1 1 1
b 0 0 1 1 0 0 1 1
c 0 1 0 1 0 1 0 1
r 0 1 1 0 1 0 0 1
当结果为1的时候a,b,c有两种可能，1种是0 0 1 还有1种是 1 1 1这就没法辨别是哪一种情况了，比较辣手
网上有种方法是不管372101，先按 0 0 1这类情况算，然后得出的ans1和ans2比较 再分多种情况，比较复杂。
下面这类用到了反证法还有函数构造进程比较复杂，如果理解了，直接就噜出来了，比较推荐
1. 首先异或所有数 x=a^b^c.....其他异或=0
2. 再次用x异或所有数 x^a[i] 。 这样对出现偶数次的没有区分，由于我们不关心他们的实际大小
但是 x^a, x^b , x^c 这3个数 就起到了很大的变化。我们的目标是将这3个数划分成唯1的两组。
我们会发现 x^a ^ x^b ^ x^c =0, 而且3个数都不可能为0，而且互不相同。(由于x^a=b^c,b不等于c所以b^c不等于0)
然后做1个技能，令 n1=f(x^a),n2=f(x^b),n3=f(x^c),ni=f(x^a[i]) 其中f的作用是保存低位最近那个1其他全为0 ( XXXXX1000变成 000001000)
然后n1,n2,n3中就都有且只有1个位为1,现在区分n1,n2,n3的问题又成为
n1 0 0 0 0 1 1 1 1
n2 0 0 1 1 0 0 1 1
n3 0 1 0 1 0 1 0 1
r 0 1 1 0 1 0 0 1
之前是3个数可能同时为1，也可能只有1个为1，这样r=1; 但是3个数不可能同时为1. 不然与n1^n2^n3=0矛盾(由于x^a ^ x^b ^ x^c =0保证了任意1位上不可能3个1)
终究：
只需要 p=f(n1^n2^n3) 挑选 p&f(x^a[i])!=0 为1组 ==0为1组就好了
*/
void findthree(int a[], int n)
{
int x = findone(a, n);
int p = 0;
for (int i = 0; i < n; i++)
p ^= findbit1(x^a[i]);
p = findbit1(p);
int ans1 = 0, ans2 = 0, ans3 = 0;
for (int i = 0; i < n; i++)
{
if (p&findbit1(x^a[i]))
ans1 ^= a[i];
}
cout << ans1 << endl;
//将ans1踢出
for (int i = 0; i < n; i++)
{
if (ans1 == a[i])
{
swap(a[i], a[n - 1]);
break;
}
}
findtwo(a, n - 1);
}
int main(){
int a1[] = { 1, 1, 2, 2, 3, 4, 4 };
int a2[] = { 1, 1, 2, 2, 3, 4, 4 ,5};
int a3[] = { 6, 1, 1, 2, 2, 3, 4, 4, 5 };
cout << "找1个" << endl;
cout << findone(a1, sizeof(a1) / sizeof(int))<<endl;
cout << "找两个" << endl;
findtwo(a2, sizeof(a2) / sizeof(int));
cout << "找3个" << endl;
findthree(a3, sizeof(a3) / sizeof(int));
getchar();
getchar();
return 0;
}
上一篇 互联网定律
下一篇 Linux 文本编辑工具vim
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
