Exchange blogroll： http://laker.me/blog
Github：https://github.com/younglaker
Description
Given a nonempty 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
Solution:
https://github.com/younglaker/leetcode/blob/master/38_Count_and_Say.py
Approach 1  Array


Use array(in Python called list) to store numbers in nums. If some number in nums
is new to array, append it.If some number is already in the array, remove it
 Time complexity : O(n^2).
for i in nums
takes O(n) time, andif i in list
is also a forloop taking O(n) time.  Space complexity : O(n). We need a list of size n to contain elements in nums.
Approach 2  Hash


or:


Use array(in Python called list) to store numbers in nums. If some number in nums
is new to array, append it.If some number is already in the array, remove it
 Time complexity : O(n).
for i in nums
takes O(n) time, andif dict.has_key(i)
takes O(1) time.  Space complexity : O(n). We need a hash table of size n to contain elements in nums.
Approach 3: Math


2∗(a+b+c)−(2a+2b+c)=c
 Time complexity : O(n + n) = O(2n)=O(n).
sum()
is a forloop.  Space complexity : O(n + n) = O(2n)=O(n). A set needs space for the elements in nums
Approach 4: XOR
Because a⊕0=a
and a⊕a=0
Then: a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
So we can XOR all bits together to find the unique number.


本文原创自http://laker.me/blog，转载请注明出处，欢迎交换友链
如果本文对您有帮助，微信扫一扫，请我吃个鸡腿吧