剑指offer编程题—数组中只出现一次的树

题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路
因为题目中讲明数组中只有两个数字只出现一次，并且其他数字都出现了两次，因此这里可以使用辅助空间，时间复杂度为O(n)，当然这里忽略了容器的操作时间。
使用set容器存储遍历过的数组中的元素，set容器中不会出现重复的元素v，当想set中插入一个已经存在的元素时，插入函数会返回一个指向已经存在元素的迭代器，因此可删除这个迭代器指向的元素，最后set容器中只剩下两个只出现一次的元素。
set容器中insert(value)函数返回的结果是一个pair对象，插入成功时，pair.second=true,pair.first是一个迭代器，指向当前插入成功的元素。插入失败时，pair.second=false,pair.first指向set中已经存在的与当前插入元素相等的的元素。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len=data.size();
        *num1=0,*num2=0;
        if(len<2) return ;
        set<int> st;
        pair<set<int>::iterator,bool> p;
        for(int i=0;i<len;++i){
            p=st.insert(data[i]);
            if(!p.second){ //插入失败，当前插入元素为数组中的重复元素
                st.erase(p.first); //删除在数组中出现两次的元素
            }
        }
        //最终set容器中应该只剩下两个不重复的元素。
        *num1=*(st.begin());
        *num2=*(++st.begin());
    }
};

解题思路2
使用位运算中的异或运算，
异或运算的性质：两个数字异或，对应位相同为0，不同为1.
大致分三步进行：

1. 首先将数组中所有数字相异或，则最后的结果肯定是那两个只出现一次的数字异或的结果。
2. 根据异或结果最低位1出现的位置，可以将原数组中的元素分为两部分，每一部分中都只包含两类元素:
   1）成对出现的元素；
   2）一个只出现一次的元素，因为在异或结果最低位1出现的位置上，两个只出现一次的元素在该位置上的值肯定不同，一个为1，一个为0，不然异或结果就不会为1，所以最终两个只出现一次的元素肯定不会分到同一部份，而是在两部分中各有一个；
3. 再分别对这两部分进行异或运算，最终的结果分别为数组中两个只出现一次的元素。

class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        int len=data.size();
        *num1=0,*num2=0;
        if(len<2) return ;
        int res=0;
        for(int i=0;i<len;++i){
            res ^= data[i];  //res最终为数组中指出一次的两个数字异或的结果
        }
        int p=1;
        while(!(res&p)) p<<=1; //找到res二进制表示中最左边的1的位置
        for(int i=0;i<len;++i){
            ((data[i]&p)? *num1:*num2) ^= data[i]; //分别计算两部分异或的结果
        }
    }
};