DAY 16
1
Software Development

## [Day 16] 從LeetCode學演算法 - 0136. Single Number (Easy)

``````Question:
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
``````

(對單一數字，所以每個數字都做完就是O(N^2))，

``````a XOR a = 0
``````

``````11        = 1011
11        = 1011
11 XOR 11 = 0000 = 0
``````

``````0 XOR a = a, a XOR 0 = a
``````

``````a XOR b = b XOR a (交換律)
``````

(因每個位元的結果端看該位元總共有奇數或偶數個1，和順序無關)

``````(a XOR b) XOR c = a XOR (b XOR c) = a XOR (c XOR b) = a XOR c XOR b
``````

(不論哪邊先做，結果都是看有奇數個1->結果是1，偶數個1->結果是0)
(最前面的部分是標準的結合律)

r XOR a XOR a XOR b XOR b XOR c XOR c ……的形式。
(因為怎麼換都不應該影響結果)

(其它的兩兩XOR後會變0)

Java的部分用了語法蜜糖
int e:nums代表自nums陣列按順序每次拿一個數並交給e。

Java:

``````class Solution {
public int singleNumber(int[] nums) {
int single = 0;
for (int e:nums) single ^= e;
return single;
}
}
``````

Python:

``````class Solution:
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = nums[0]
for i in range(1, len(nums)):
res ^= nums[i]
return res
``````

「時間/空間複雜度？」
(由於只要整個陣列掃過一次就結束了且無須額外的陣列空間，

0098. Validate Binary Search Tree (Medium)