136. Single Number

136. Single Number  

( https://leetcode.com/problems/single-number/description/ )

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

You must implement a solution with a linear runtime complexity and use only constant extra space.

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

Constraints:

1 <= nums.length <= 3 * 104

-3 * 104 <= nums[i] <= 3 * 104

Each element in the array appears twice except for one element which appears only once.

思路筆記:
任何數字 XOR 自己，會等於 0

任何數字 XOR 0 會等於自己

所以你只要把陣列裡面所有的數字 XOR 起來

出現兩次的數字就會變成 0

出現一次的數字跟其他的 0，XOR 起來還是原本的數字

那我們就得到答案了

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        int ans = nums[0];

        for(vector<int>::iterator it = nums.begin() + 1; it != nums.end(); it++)

        {

            ans ^= *it;

        }

        return ans;

    }

};

參考：

https://www.youtube.com/watch?v=Hy1hE0HBR3U&list=PLY_qIufNHc29OLToHki4t0Z5KIhUzdYxD&index=1