LeetCode 136. Single Number [Easy] [C++] 解題筆記

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

想法:

    這題簡單的作法就是另開一個array算出現次數或是先 sort 在遍歷，但題目要求 O(n) time, O(1) space，

前者需要 O(n) space，後者需要 O(nlogn) time。因此這題必須使用 "bitwise operation"，坦白說我也想不大到

要這樣子來解，反正我們知道對兩個相同數字做 XOR 運算會得到 0 因為 1 xor 1 = 0，因此我們就只需要把所有個數字都 xor

起來，這樣最後的結果就會留下不重複的那個數字，因為重複的數字的每個位元都會出現 2 的倍數，只有不重複的數字的每個位元

會出現奇數次。

完整程式碼:

/* bitwise operation
 * A XOR A = 0  
 *
*/
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        for (size_t i = 1; i < nums.size(); i++) {
            nums.at(0) ^= nums.at(i);
        }
        return nums.at(0);
    }
};