136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Subscribe to see which companies asked this question.

题意解析：
给一组数，除了一个数字外，每个数字都出现两次，求其中只出现了一次的数字。

解题思路：

• 原本考虑简单的按照数字的值建立哈希表，但用了一下超过内存限制，应该还是使用map，按照value，count的方式去存储，然后遍历map，获得count为1的那个value。
• 又想到除了一个数字外，每个数字都出现两次，那么可以用一个集合，维护当前只出现一次的数字，当发现再次遇到这个数字，就从集合里面删掉这个数字，这样遍历一边就只剩下那个只出现了一次的数字了，不过这样也需要使用O(n)大小的内存。
• 最后查看参考答案，原来对每个元素使用XOR操作即可解决问题。每个数字和自己做XOR得到0，而0和一个数字XOR得到该数字。又因为XOR操作满足算术中的交换律和结合律，所以计算的顺序可以不用考虑。

//维护一个当前只出现了一次的集合
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        set<int> current;
        for(int i = 0; i < nums.size();i++) {
            if(current.count(nums[i])!=1) {
                current.insert(nums[i]);
            }else{
                current.erase(nums[i]);
            }
        }
        return *current.begin();
    }
};

//异或
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int number = 0;
        for(int i = 0; i < nums.size();i ++) {
            number = number xor nums[i];
        }
        return number;
    }
};

137. Single Number II

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

题意解析：
给一组数，除了一个数字外，每个数字都出现三次，求其中只出现了一次的数字。

解题思路：

• 类似上题思路，改成保存出现了一次和出现了两次的两个集合。
• 一个int类型为32位二进制数，那么对于每一位上的数进行求和，如果出现了三次则可以模除3，那么正好得到了只出现了一次的数字。

//出现了一次once和出现了两次twice的两个集合。
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        set<int> twice;
        set<int> once;
        for(int i = 0; i<nums.size(); i++) {
            int a = nums[i];
            if(twice.count(a)== 1) {
                twice.erase(a);
            } else if(once.count(a)==1) {
                twice.insert(a);
                once.erase(a);
            } else {
                once.insert(a);
                cout<<a;
            }
        }
        return *once.begin();

    }
};

//使用位运算
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> bits(32);
        int result = 0;
        for(int i = 0; i<32; i++) {
            for(int j = 0; j < nums.size(); j++) {
                if((nums[j]>>i) & 1) {
                    bits[i]++;
                }
            }
            result |= ((bits[i]%3) << i);
        }

        return result;
    }
};

Bit Manipulation(位运算)：

一共五种运算：与，或，异或，左移，右移。

常用技巧：

1. n & （n-1）能够消灭n中最右侧的一个1。
2. 右移：除以2， 左移：乘以2。
3. 异或性质：交换律，0^a=a, a^a=0;
4. 将常用字符、数字等均转为按位运算，可以节约空间。