程序员人生网站导航
算法-找出其他出现偶数次的数组中出现1次，2次，3次的数

栏目：php教程时间：2015-06-11 08:14:42
#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
------分隔线----------------------------