面试40-一个数组，有2个数字出现奇数次，其余都是偶数次，求这两个数字O(n) O(1)

#include<iostream>

using namespace std;

// 题目：数组中只有不多于两个数字出现次数是奇数次，其他都是偶数次，求出出现奇数次的数字(不含0的数组)

//思想：

/*

（1）如果只有一个数字是奇数次，直接对数组进行按位异或运算，得到的结果就是该数

（2）如果有俩个，可以先对数组异或，得到的结果（就是两个奇数次的数字异或的结果），必定至少包含一个1，可以根据这个1在的位置，把数组分为两个部分

     则两个奇数次的数字必定分别在两个部分，而相同的数次必定在同一组，则可以对两个部分分别求异或得到答案

*/

int findNumsAppear(int arr[],int len,pair<int,int>& st);// 返回0表示没有，1表示一个，2表示2个,-1表示参数错误，没有考虑更多的情况

int count1(int num);// 统计int在内存中1的个数

int main()

{

    pair<int,int>st;

    st.first=0x80000000;

    st.second=0x80000000;

    int arr[]={,,,,,,,,,,,,,,,,,,,,,,,,,};

    cout<<findNumsAppear(arr,sizeof(arr)/sizeof(int),st)<<endl;

    cout<<st.first<<"   "<<st.second<<endl;

    return ;

}

int findNumsAppear(int arr[],int len,pair<int,int>& st)

{

    if(arr==NULL||len<=)

        return -;

    int num=arr[];

    int count=;

    for(int i=;i<len;i++)

        num^=arr[i];

    if(num==)

        return ;

    else  // 找到num 中第一个1，让其他位置1为0   此处参考count1的方法

    {

        while(num)

        {

            if((num&(num-))==)

                break;

            else

                num=num&(num-);   // 最终会保留下最高位的一个1，用来划分数组

        }

    }

    int i=;int j=len-;

    int tmp;

    while(i<j)   // 循环最终结果为i==j 左半边数组的最后个元素下标

    {

        while(i<j&&(arr[j]&num)==)

            j--;

        while(i<j&&(arr[i]&num)==num)

            i++;

        if(i<j)

        {

            tmp=arr[i];

            arr[i]=arr[j];

            arr[j]=tmp;

        }

    }

    int num1=arr[];

    for(int k=;k<=i;k++)

        num1^=arr[k];

    int num2=arr[len-];

    for(int k=len-;k>i;--k)

        num2^=arr[k];

    if(num1!=)

        st.first=num1;

    if(num2!=)

        st.second=num2;

    if(num1!=&&num2!=)

        return ;

    else return ;

}

int count1(int num) // 如果不许用位运算，直接 unsigned int n=(unsigned int)num; 用%  / 计算    -1内存全部为FFFFFFFF 转为最大的unsigned int

{

    int count=;

    while(num)

    {

        ++count;

        num=num&(num-);

    }

    return count;

}

面试40-一个数组，有2个数字出现奇数次，其余都是偶数次，求这两个数字O(n) O(1)的相关教程结束。