Leetcode.136.Single Number

题目

给定一个非空数组, 数组中除了一个数字出现1次, 其他数字都出现2次.
找出出现一次的数字.

Input: [2,2,1]
Output: 1
Input: [4,1,2,1,2]
Output: 4

思路1

map, 第1次出现加入map, 第2次出现移除map, 最后只剩一个元素
时间复杂度O(2n)
空间复杂度O(n)

int singleNumber(vector<int>& nums) {
    map<int, bool> m;
    for (int i = 0; i < nums.size();i++) {
        if (m[nums[i]]) {
            m.erase(nums[i]);
        } else {
            m[nums[i]] = true;
        }
    }

    return (int)(m.begin()->first);
}

思路2

set, 2 (a + b + c) - (a+a+b+b+c) = c.
时间复杂度O(2n)
空间复杂度O(n)

int singleNumber(vector<int>& nums) {
    set<int> s;
    int num = 0;
    for (int i = 0; i < nums.size();i++) {
        num -= nums[i];
        s.insert(nums[i]);
    }
    set<int>::iterator iter = s.begin();
    while (iter != s.end()) {
        num += *iter * 2;
        iter++;
    }

    return num;
}

思路3

异或, a ^ b = a + b, a ^ a ^ b = b.
时间复杂度O(n)
空间复杂度O(1)

int singleNumber(vector<int>& nums) {
    int res = 0;
    cout << endl;
    for (int num : nums) {
        res ^= num;
        cout  << num << " | " << res << endl ;
    }

    return res;
}

总结

熟练掌握位运算, 位运算在有些情况下具有神奇的效果.