Single Number

本文是在學習中的總結，歡迎轉載但請注明出處：http://blog.csdn.net/pistolove/article/details/42713315

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?

思路：

（1）題意為給定1個整形數組，其中數組中除1個元素以外，其它任意元素都出現兩次，求只出現1次的元素。

（2）由于題目限制了時間復雜度為線性的，即不能出現屢次for循環，且建議最好不要申請額外的空間。這樣，我們就需要思考，如何在遍歷數組1次的情況下找出出現1次的元素。斟酌到能否想辦法把相同的元素都消除掉，這里我們就需要應用不常見的特殊運算符“^”― 按位異或運算。我們知道異或運算相同的位會消除，例4^4=(2進制)10^(2進制)10=(2進制)00，這樣就消除相同的數字。即便數組中相同數字是非連續的，根據加法的交換律，能夠得到一樣的結果。

（3）希望本文對你有所幫助。

算法代碼實現以下：

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈