寻找唯一值

题目描述

找出数组中唯一的值，因为该数组除了那个值以外，其他的值都有两个。

例如：arr = {1,1,2,2,3}, 找出数字3

利用异或运算的性质

异或运算

异或运算满足交换律和结合律（对于二进制的每一位，异或运算相当于差的绝对值

a^b = b^a, a^b^c = a^(b^c)

a^a=0 （自己和自己一定相同）

0^a=a （0^0=0, 0^1=1）

int single_number(vector<int> arr){
    int a = arr[0];
    if(arr.size() == 1)return a;
    for(int i = 1; i < arr.size(); i++){
        a ^= arr[i];
    }
    return a;
}

解释：

设数组中的数为b,b,c,c,e,d,e… …，则a = b^b^c^c^e^d^e^… … = 0^0^e^e^d^… … = 0^0^0^d^0^… … = d，因此遍历完所有数据后，得到的结果就是唯一值。

位运算的一些常见用法

• 除以2：n >> 1
• 判断奇偶：n & 1为true代表该数是奇数，否则为偶数
• 交换数据：a ^= b, b ^= a, a ^= b

利用哈希表

哈希表

对于遍历的每一个元素，如果哈希表中不存在该元素，则添加；否则在哈希表中删除该元素

int single_number2(vector<int> arr){
    unordered_set<int> my_set;
    for(auto it = arr.begin(); it != arr.end(); it++){
        if(my_set.count(*it) > 0){
            my_set.erase(*it);
        } else {
            my_set.insert(*it);
        }
    }
    return *my_set.begin();
}