0136. 只出现一次的数字
题目地址(136. 只出现一次的数字)
题目描述
1
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
2
3
说明：
4
5
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
6
7
示例 1:
8
9
输入: [2,2,1]
10
输出: 1
11
示例 2:
12
13
输入: [4,1,2,1,2]
14
输出: 4
Copied!
前置知识
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
根据题目描述，由于加上了时间复杂度必须是 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：
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
var singleNumber = function (nums) {
6
let ret = 0;
7
for (let index = 0; index < nums.length; index++) {
8
const element = nums[index];
9
ret = ret ^ element;
10
}
11
return ret;
12
};
Copied!
C Code：
1
int singleNumber(int* nums, int numsSize){
2
int res=0;
3
for(int i=0;i<numsSize;i++)
4
{
5
res ^= nums[i];
6
}
7
8
return res;
9
}
Copied!
C++ Code：
1
class Solution {
2
public:
3
int singleNumber(vector<int>& nums) {
4
auto ret = 0;
5
for (auto i : nums) ret ^= i;
6
return ret;
7
}
8
};
9
10
// C++ one-liner
11
class Solution {
12
public:
13
int singleNumber(vector<int>& nums) {
14
return accumulate(nums.cbegin(), nums.cend(), 0, bit_xor<int>());
15
}
16
};
Copied!
Java Code：
1
class Solution {
2
public int singleNumber(int[] nums) {
3
int res = 0;
4
for(int n:nums)
5
{
6
// 异或
7
res ^= n;
8
}
9
return res;
10
}
11
}
Copied!
Python Code:
1
class Solution:
2
def singleNumber(self, nums: List[int]) -> int:
3
single_number = 0
4
for num in nums:
5
single_number ^= num
6
return single_number
Copied!
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(1)$
延伸
有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
和上面一样，只是这次不是一个数字，而是两个数字。还是按照上面的思路，我们进行一次全员异或操作， 得到的结果就是那两个只出现一次的不同的数字的异或结果。
我们刚才讲了异或的规律中有一个
任何数和本身异或则为0， 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。 分组需要满足两个条件.- 1.两个独特的的数字分成不同组
- 2.相同的数字分成相同组
这样每一组的数据进行异或即可得到那两个数字。
问题的关键点是我们怎么进行分组呢？
由于异或的性质是，同一位相同则为 0，不同则为 1. 我们将所有数字异或的结果一定不是 0，也就是说至少有一位是 1.
我们随便取一个， 分组的依据就来了， 就是你取的那一位是 0 分成 1 组，那一位是 1 的分成一组。 这样肯定能保证
2. 相同的数字分成相同组, 不同的数字会被分成不同组么。 很明显当然可以， 因此我们选择是 1，也就是 说两个独特的的数字在那一位一定是不同的，因此两个独特元素一定会被分成不同组。Done！
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
最近更新 1yr ago