題目描述：

給你一個?非空?整數(shù)數(shù)組?nums?，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。

你必須設(shè)計(jì)并實(shí)現(xiàn)線性時(shí)間復(fù)雜度的算法來解決此問題，且該算法只使用常量額外空間。

示例 1 ：

輸入：nums = [2,2,1]
輸出：1

示例 2 ：

輸入：nums = [4,1,2,1,2]
輸出：4

示例 3 ：

輸入：nums = [1]
輸出：1

提示：

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。

通過次數(shù)

975.3K

提交次數(shù)

1.3M

通過率

72.8%

思路和題解：

思路一：暴力枚舉：

每次從數(shù)組中取出一個數(shù)，然后從剩余的數(shù)中查找，如果找不到就說明這個數(shù)只出現(xiàn)一次。時(shí)間復(fù)雜度O（n^2）,空間復(fù)雜度O（1），時(shí)間復(fù)雜度不符合要求

思路二：排序

數(shù)組中只有一個數(shù)出現(xiàn)了一次，其余都出現(xiàn)了兩次，可以先將數(shù)組排序，然后再遍歷一次數(shù)組，如過某個數(shù)字和前面的數(shù)后面的數(shù)都不想等，那就是只出現(xiàn)一次的數(shù)。時(shí)間復(fù)雜度O(nlog n),空間復(fù)雜度O(1),空間復(fù)雜度符合條件，時(shí)間復(fù)雜度不知道不知道算不算線性。

思路三：建立映射表

建立一個map，遍歷每一個數(shù)字，遍歷時(shí)查找有無該數(shù)對應(yīng)的鍵，如果有就刪除，如果無就加入，遍歷完后剩下的那個就是只出現(xiàn)一個的數(shù)。

思路四：位運(yùn)算

先將要返回的數(shù)字ans設(shè)為0，ans依次與數(shù)組里的每一個數(shù)進(jìn)行按位異或運(yùn)算，由于異或運(yùn)算是可交換的，運(yùn)算完成后，出現(xiàn)兩次的數(shù)會因?yàn)槊恳晃欢枷嗤優(yōu)?，出現(xiàn)一次的數(shù)和0進(jìn)行異或位運(yùn)算而保留下來。時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)，都符合要求。代碼：

class Solution{
public:int singleNumber(vector<int>& nums){int ans=0;for(int i=0;i<nums.size();i++)ans^=nums[i];return ans;}
};