# 136 Single Number

Given a non-empty 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?

Example 1:

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

Example 2:

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

這題是easy的，但我想了2個小時，才把解出我的解答。但若nums長度等於1的話就不用以下迴圈尋找，直接回傳nums[0]，長度為1，當然一定是單一值。接著我用的是用先排序的方式，再用for迴圈(i 初值為1，每次遞增2 ex: 1,1,2,2,3,3檢查1vs1 , 2vs2...; ex 1,1,5,6,6檢查1vs1 , 5vs6, 回傳5即可)nums[i-0]、nums[i]相比，因為題目題說一整個陣列只有一個數字是單一的，所以當找到時不一樣時，當下立刻回傳nums[i-0]，for迴圈結束沒有找到單一的數，因為只剩nums[ nums.length-1 ]沒有遍尋到，所以單一的一定在最後一個位置。回傳nums[ nums.length-1 ]，time conplexity 是3ms 大於44.16%的解法，space complexity是38.8MB

程式碼:

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
      Arrays.sort(nums);
        for(int i = 1; i< nums.length ; i=i+2){
            if(nums[i-1] !=nums[i]){
                return nums[i-1];
            }
        }
        return nums[nums.length-1];
    }
}

但討論區及解答，解法如下:

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i: nums){
            ans = ans ^ i;
        }
        return ans;
    }
}
EX: 3,3,4,5,5
ans ^ i 運算 ==> 0^3
000  --ans
011  --3
-------------
011  --ans ==> 3

ans ^ i 運算 ==> 3^3
011  --ans
011  --3
-------------
000  --ans 0

ans ^ i 運算 ==> 0^4
000  --ans
100  --4
-------------
100  --ans 4

ans ^ i 運算 ==> 4^5
100  --ans
101  --5
-------------
001  --ans 1

ans ^ i 運算 ==> 1^5
001  --ans
101  --5
-------------
100  --ans 4

運用XOR互斥或閘 A ^ A = 0 ，A^ 0 = A，符合交換率。

參考資料:java的四種2數相加