136. Single Number

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

constant extra space

題目限制不會變動的空間，例如array，會變動的空間像是vector的push_back就不行。

解法一

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        
        int arr_pos[3*10000+1] = {0};
        int arr_neg[3*10000] = {0};
        
        for(int i=0; i<nums.size(); i++){
            if(nums[i] >= 0){
                arr_pos[nums[i]]++;
            }
            else{
                arr_neg[-(nums[i])]++;
            }
        }
       
        for(int i=0; i<=3*10000; i++){
            if(arr_pos[i] == 1){
                return i;
            }
            
            if(arr_neg[i] == 1){
                    return -i;
            }
        }
        return 0;
    }
};

解法二

使用XOR解

XOR Truth Table

以example 2為例:

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

由左至右，計算如下，有黃色標示為輸入數字，未標示者為res