0136. 只出現一次的數字 · ttttt

# 0136. 只出現一次的數字 ## 題目地址(136. 只出現一次的數字) <https://leetcode-cn.com/problems/single-number/> ## 題目描述 ``` <pre class="calibre18">``` 給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。說明：你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現嗎？示例 1: 輸入: [2,2,1] 輸出: 1 示例 2: 輸入: [4,1,2,1,2] 輸出: 4 ``` ``` ## 前置知識 - [位運算](https://github.com/azl397985856/leetcode/blob/master/thinkings/bit.md) ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路根據題目描述，由于加上了時間復雜度必須是 O(n)，并且空間復雜度為 O(1)的條件，因此不能用排序方法，也不能使用 map 數據結構。我們可以利用二進制異或的性質來完成，將所有數字異或即得到唯一出現的數字。 ## 關鍵點 1. 異或的性質兩個數字異或的結果`a^b`是將 a 和 b 的二進制每一位進行運算，得出的數字。運算的邏輯是如果同一位的數字相同則為 0，不同則為 1 2. 異或的規律 3. 任何數和本身異或則為`0` 4. 任何數和 0 異或是`本身` 5. 很多人只是記得異或的性質和規律，但是缺乏對其本質的理解，導致很難想到這種解法（我本人也沒想到） 6. bit 運算 ## 代碼 - 語言支持：JS，C，C++，Java，Python JavaScrip Code： ``` <pre class="calibre18">``` /** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { let ret = 0; for (let index = 0; index < nums.length; index++) { const element = nums[index]; ret = ret ^ element; } return ret; }; ``` ``` C Code： ``` <pre class="calibre18">``` int singleNumber(int* nums, int numsSize){ int res=0; for(int i=0;i<numsSize;i++) { res ^= nums[i]; } return res; } ``` ``` C++ Code： ``` <pre class="calibre18">``` class Solution { public: int singleNumber(vector<int>& nums) { auto ret = 0; for (auto i : nums) ret ^= i; return ret; } }; // C++ one-liner class Solution { public: int singleNumber(vector<int>& nums) { return accumulate(nums.cbegin(), nums.cend(), 0, bit_xor<int>()); } }; ``` ``` Java Code： ``` <pre class="calibre18">``` class Solution { public int singleNumber(int[] nums) { int res = 0; for(int n:nums) { // 異或 res ^= n; } return res; } } ``` ``` Python Code: ``` <pre class="calibre18">``` class Solution: def singleNumber(self, nums: List[int]) -> int: single_number = 0 for num in nums: single_number ^= num return single_number ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 延伸有一個 n 個元素的數組，除了兩個數只出現一次外，其余元素都出現兩次，讓你找出這兩個只出現一次的數分別是幾，要求時間復雜度為 O(n) 且再開辟的內存空間固定(與 n 無關)。和上面一樣，只是這次不是一個數字，而是兩個數字。還是按照上面的思路，我們進行一次全員異或操作，得到的結果就是那兩個只出現一次的不同的數字的異或結果。我們剛才講了異或的規律中有一個`任何數和本身異或則為0`，因此我們的思路是能不能將這兩個不同的數字分成兩組 A 和 B。分組需要滿足兩個條件. 1. 兩個獨特的的數字分成不同組 2. 相同的數字分成相同組這樣每一組的數據進行異或即可得到那兩個數字。問題的關鍵點是我們怎么進行分組呢？由于異或的性質是，同一位相同則為 0，不同則為 1. 我們將所有數字異或的結果一定不是 0，也就是說至少有一位是 1. 我們隨便取一個，分組的依據就來了，就是你取的那一位是 0 分成 1 組，那一位是 1 的分成一組。這樣肯定能保證`2. 相同的數字分成相同組`, 不同的數字會被分成不同組么。很明顯當然可以，因此我們選擇是 1，也就是說`兩個獨特的的數字`在那一位一定是不同的，因此兩個獨特元素一定會被分成不同組。 Done！更多題解可以訪問我的LeetCode題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經37K star啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)