#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 程序員人生 版權所有
