136. Single Number

Leetcode Day 1

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

1. python

• 1.1 List operation

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        no_duplicate_list = []
        for i in nums:
            if i not in no_duplicate_list:
                no_duplicate_list.append(i)
            else:
                no_duplicate_list.remove(i)
        return no_duplicate_list.pop()

• 1.2 Bit Manipulation
  ⊕是XOR运算：异或运算就是如果两个数字（0或者1）相同,则输出为0; 如果两个数字（0或者1）不相同,就输出为a
  • a⊕0=a
  • a⊕a=0
  • a⊕b⊕a= (a⊕a)⊕b=b

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        a = 0
        for i in nums:
            a ^= i
        return a

2. C++

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        // XOR (^) is both commutative and associative 
        // The numbers which appear twice will be cancelled
        // Only the number that appear twice survive 
        int value = 0;
        int i, n;
        n = nums.size();
        for(i=0; i<n; i++)
            value = value ^ nums[i];
        return value;
    }
};