数组中数字出现的次数

1. 给定一个数组, 假设其中有两个数只出现了一次, 其它均出现了两次, 让找出只出现了一次的两个数字.

对于数字出现次数, 可从异或角度出发. 当数组中只有一个数字出现一次, 其余全为2次时, 直接异或可得结果. 当有两个数字出现一次时, 最后的异或结果必为此两数的异或结果. 找到异或结果二进制表示中第一个1出现的位置, 以此位置将原数组划分为两组, 此两数必被划分开. 然后对两组数分别异或可得结果.

void f(vector<int> arr){
    int x_or=arr[0];
    for(int i=1;i<arr.size();i++){
        x_or = x_or ^ arr[i];
    }
    int index=0;
    unsigned int flag=1;
    while(!x_or & flag){
        index++;
        flag = flag <<1;
    }
    vector<int> group1;
    vector<int> group2;
    int split_num = pow(2, index);
    for(int i=0;i<arr.size();i++){
        if(arr[i] & split_num){
            group1.push_back(arr[i]);
        } else{
            group2.push_back(arr[i]);
        }
    }
    int val1=group1[0], val2=group2[0];
    for(int i=1;i<group1.size();i++){
        val1 = val1 ^ group1[i];
    }
    for(int i=1;i<group2.size();i++){
        val2 = val2 ^ group2[i];
    }
    cout<<val1<<" : "<<val2<<endl;
}

2.数组中唯一出现一次的数字

给定一个数字序列, 除了一个数字外其余均出现3次, 找出只出现了一次的数

第一个能想到的就是利用哈希表, 记录每一个数字出现的次数, 时间与空间复杂度均为 O(n). 另, 从二进制考虑, 每个数字出现3次, 如果对所有数字的二进制的每一位求和, 那么必为3的倍数, 否则, 该只出现一次的数字的该二进制位必为1, 便可得到该数的二进制表示.