题目描述
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
难度:Middle
前置知识
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
根据题目描述,由于加上了时间复杂度必须是 O(n),并且空间复杂度为 O(1)的条件,因此不能用排序方法,也不能使用 map 数据结构。
我们可以利用二进制异或的性质来完成,将所有数字异或即得到唯一出现的数字。
关键点
- 异或的性质
两个数字异或的结果a^b
是将 a 和 b 的二进制每一位进行运算,得出的数字。 运算的逻辑是
如果同一位的数字相同则为 0,不同则为 1 -
异或的规律
-
任何数和本身异或则为
0
-
任何数和 0 异或是
本身
-
很多人只是记得异或的性质和规律,但是缺乏对其本质的理解,导致很难想到这种解法(我本人也没想到)
-
bit 运算
代码
- 语言支持:JS,C,C++,Java,Python
JavaScrip Code:
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:是以前端进阶资源教程分享为主的专业网站,包括:前端、大厂面试题、typescript教程、程序人生、React.js
* @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:
int singleNumber(int* nums, int numsSize){
int res=0;
for(int i=0;i<numsSize;i++)
{
res ^= nums[i];
}
return res;
}
C++ Code:
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:
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int n:nums)
{
// 异或
res ^= n;
}
return res;
}
}
Python Code:
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(1)$
延伸
有一个 n 个元素的数组,除了两个数只出现一次外,其余元素都出现两次,让你找出这两个只出现一次的数分别是几,要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。
和上面一样,只是这次不是一个数字,而是两个数字。还是按照上面的思路,我们进行一次全员异或操作,
得到的结果就是那两个只出现一次的不同的数字的异或结果。
我们刚才讲了异或的规律中有一个任何数和本身异或则为0
, 因此我们的思路是能不能将这两个不同的数字分成两组 A 和 B。
分组需要满足两个条件.
- 两个独特的的数字分成不同组
-
相同的数字分成相同组
这样每一组的数据进行异或即可得到那两个数字。
问题的关键点是我们怎么进行分组呢?
由于异或的性质是,同一位相同则为 0,不同则为 1. 我们将所有数字异或的结果一定不是 0,也就是说至少有一位是 1.
我们随便取一个, 分组的依据就来了, 就是你取的那一位是 0 分成 1 组,那一位是 1 的分成一组。
这样肯定能保证2. 相同的数字分成相同组
, 不同的数字会被分成不同组么。 很明显当然可以, 因此我们选择是 1,也就是
说两个独特的的数字
在那一位一定是不同的,因此两个独特元素一定会被分成不同组。
Done!
- 原题leetcode链接:https://leetcode-cn.com/problems/single-number/
- 更多力扣 解题: 力扣 – 全球极客挚爱的技术成长平台 ,也可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books,标星关注一起学习更多前端前沿知识。
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com