題目:
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?
思路:
這一題原來聽過,對位運算敏感度人可能會想到兩個相等的數進行異或運算結果為零,而零與任何不為零的數異或運算結果都為這個不為零的數本身,基於此,把數組內所有元素串聯進行異或,那些配對的經過異或都變成零了,而落單的最終一定是和零進行異或,結果必然是它自己。異或的順序要不要緊呢?不要緊,異或運算是有結合律的,不在意順序,所以不用在意這個細節。
代碼:
class Solution { public: int singleNumber(int A[], int n) { int re; for(int i=0;i