148 lines
3.9 KiB
Markdown
148 lines
3.9 KiB
Markdown
|
## 题目地址
|
|||
|
|
|
|||
|
|
https://leetcode.com/problems/single-number/description/
|
|||
|
|
|
|||
|
|
## 题目描述
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
Given a non-empty 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?
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
根据题目描述，由于加上了时间复杂度必须是 O(n)，并且空间复杂度为 O(1)的条件，因此不能用排序方法，也不能使用 map 数据结构。
|
|||
|
|
|
|||
|
|
我们可以利用二进制异或的性质来完成，将所有数字异或即得到唯一出现的数字。
|
|||
|
|
|
|||
|
|
## 关键点
|
|||
|
|
|
|||
|
|
1. 异或的性质
|
|||
|
|
两个数字异或的结果`a^b`是将 a 和 b 的二进制每一位进行运算，得出的数字。 运算的逻辑是
|
|||
|
|
如果同一位的数字相同则为 0，不同则为 1
|
|||
|
|
|
|||
|
|
2. 异或的规律
|
|||
|
|
|
|||
|
|
- 任何数和本身异或则为`0`
|
|||
|
|
|
|||
|
|
- 任何数和 0 异或是`本身`
|
|||
|
|
|
|||
|
|
3. 很多人只是记得异或的性质和规律，但是缺乏对其本质的理解，导致很难想到这种解法（我本人也没想到）
|
|||
|
|
|
|||
|
|
4. bit 运算
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
* 语言支持：JS，C++，Python
|
|||
|
|
|
|||
|
|
JavaScrip Code：
|
|||
|
|
```js
|
|||
|
|
/*
|
|||
|
|
* @lc app=leetcode id=136 lang=javascript
|
|||
|
|
*
|
|||
|
|
* [136] Single Number
|
|||
|
|
*
|
|||
|
|
* https://leetcode.com/problems/single-number/description/
|
|||
|
|
*
|
|||
|
|
* algorithms
|
|||
|
|
* Easy (59.13%)
|
|||
|
|
* Total Accepted: 429.3K
|
|||
|
|
* Total Submissions: 724.1K
|
|||
|
|
* Testcase Example: '[2,2,1]'
|
|||
|
|
*
|
|||
|
|
* Given a non-empty 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?
|
|||
|
|
*
|
|||
|
|
* Example 1:
|
|||
|
|
*
|
|||
|
|
*
|
|||
|
|
* Input: [2,2,1]
|
|||
|
|
* Output: 1
|
|||
|
|
*
|
|||
|
|
*
|
|||
|
|
* Example 2:
|
|||
|
|
*
|
|||
|
|
*
|
|||
|
|
* Input: [4,1,2,1,2]
|
|||
|
|
* Output: 4
|
|||
|
|
*
|
|||
|
|
*
|
|||
|
|
*/
|
|||
|
|
/**
|
|||
|
|
* @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++：
|
|||
|
|
```C++
|
|||
|
|
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>());
|
|||
|
|
}
|
|||
|
|
};
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
Python Code:
|
|||
|
|
|
|||
|
|
```python
|
|||
|
|
class Solution:
|
|||
|
|
def singleNumber(self, nums: List[int]) -> int:
|
|||
|
|
single_number = 0
|
|||
|
|
for num in nums:
|
|||
|
|
single_number ^= num
|
|||
|
|
return single_number
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
## 延伸
|
|||
|
|
|
|||
|
|
有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
|
|||
|
|
|
|||
|
|
和上面一样，只是这次不是一个数字，而是两个数字。还是按照上面的思路，我们进行一次全员异或操作，
|
|||
|
|
得到的结果就是那两个只出现一次的不同的数字的异或结果。
|
|||
|
|
|
|||
|
|
我们刚才讲了异或的规律中有一个`任何数和本身异或则为0`， 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。
|
|||
|
|
分组需要满足两个条件.
|
|||
|
|
|
|||
|
|
1. 两个独特的的数字分成不同组
|
|||
|
|
|
|||
|
|
2. 相同的数字分成相同组
|
|||
|
|
|
|||
|
|
这样每一组的数据进行异或即可得到那两个数字。
|
|||
|
|
|
|||
|
|
问题的关键点是我们怎么进行分组呢？
|
|||
|
|
|
|||
|
|
由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1.
|
|||
|
|
|
|||
|
|
我们随便取一个， 分组的依据就来了， 就是你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。
|
|||
|
|
这样肯定能保证`2. 相同的数字分成相同组`, 不同的数字会被分成不同组么。 很明显当然可以， 因此我们选择是 1，也就是
|
|||
|
|
说`两个独特的的数字`在那一位一定是不同的，因此两个独特元素一定会被分成不同组。
|
|||
|
|
|
|||
|
|
Done！
|