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個整形數(shù)組，其中數(shù)組中除1個元素以外，其它任意元素都出現(xiàn)兩次，求只出現(xiàn)1次的元素。

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

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

算法代碼實現(xiàn)以下：

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