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)