Leetcode：Single Number

Single Number

Given an 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?

Answer 

這個題目雖然標記是中等難度，但是解起來並不難，因為只要先排列後，相同數字一定相鄰，單一數字一定與相鄰數字不同，所以只要找下一個數字是不同的，那麼當前數字必定是單一數字。

Javascript

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    if(nums.length == 1){
        return nums[0];
    }
    nums.sort();

    for(var i = 0; i < nums.length ; i+=2){
        if(nums[i] != nums[i+1]){
            return nums[i];
        }
    }
};
//Min:136ms

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

而有人建議我直接用一個迴圈作 XOR 的位元運算，而得到的結果一定是 Single Number。

example
1 , 2 , 2
0x0001 , 0x0010 , 0x0010

Step 1
1 ^ 2 = 3
0x0001 ^ 0x0010 = 0x0011
Step 2
3 ^ 2 = 1
0x0011 ^ 0x0010 = 0x0001

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    if(nums.length == 1){
        return nums[0];
    }
    var x=0;

    for(var i = 0; i < nums.length ; i++){
        x = x ^ nums[i];
    }
    return x;
};
//Min:116ms

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

C

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

int singleNumber(int* nums, int numsSize) {
    //若遇只有單個數的陣列直接return
    if(numsSize == 1){
        return *nums;
    }
    
    int i, x = 0;
    for(i = 0; i< numsSize; i++ ){
        //作XOR運算
        x ^= *(nums+i);
    }
    return x;
}
//Min:8ms

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

Python

_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/_/

然後我又不知道哪根筋不對，一直把 for i in array 當作是和C語言一樣的 for( i=0; i< len(array); i++)，結果當然是一直錯，看來已經出現了語言障礙...

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if ( len(nums) == 1 ):
            return nums[0]
        
        x = 0
        for i in nums:
            x ^= i
        return x
#Min:48ms