只出现一次的数字|刷题打卡
分类:javascript
前言
本文正在参与掘金团队号上线活动,点击查看大厂春招职位。
题目
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
示例 2:
输入: [4,1,2,1,2]
输出: 4
题解
题目看着很简单,我们能想到的方法也有很多,但是,题目要求不使用额外空间,具有线性时间复杂度,这个就比较难想到了。
先来说说,如果没有这个限制,我会想到哪些方法?
方法一:利用排序
先利用排序,将数组排序好,然后因为只有一个出现一次的树,所以这个数字必定在奇数位,只要它是在奇数位,并且与后一个数不等,那就是我们要返回的数了。
但是这个方法不符合题目提出的时间、空间的要求。
所以我们想到了异或运算符。
方法二: 利用异或。
那异或的运算规则是什么样的?
相同的数异或为0,任何数与0异或为任何数。
AC代码
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let ans = 0;
for(let i = 0; i < nums.length; i++){
ans ^= nums[i];
}
return ans;
};
总结
这一题的重点就是位运算符异或!如果想不到就没法解,但凡题目要求不要额外的空间,我们就得往位运算符上靠。