LeetCode算法笔记-Day55
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?
1 | example: |
方法一:傻瓜算法
Analyse:
如果没有时间复杂度和空间复杂度的限制,这道题有很多种解法。
Answer:
1 | /** |
- 时间复杂度:O(n)
- 空间复杂度:O(n)
方法二 位运算
Analyse:
可使用异或运算。异或运算有以下三个性质:
- a⊕0 = a
- a⊕a = 0
- a⊕b⊕a = b⊕a⊕a = b⊕(a⊕a) = b⊕0 = b
假设数组中有 2m+1 个数,其中有 m 个数各出现两次,一个数出现一次。数组中的全部元素的异或运算结果总是可以写成如下形式:
化简后:
Answer:
1 | /** |
- 时间复杂度:O(n)
- 空间复杂度:O(1)