刷 只出现一次的数字 | 刷题打卡
一、题目描述:
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
二、思路分析:
只有一项出现一次,其他都出现两次,想到Hash存储
思路:
- 设置一个hash对象
- 遍历数组
- 对象有当前项的key的话,表示不符合要求,遂删除
- 没有当前项的key的话,先建立key
- 遍历之后,对象只有一个key,就是要的答案
空间是O(n),时间也是O(n)。
评论区说了异或运算,再问问对象,异或有个显著特征,就是异或2次相同的数,等于没有异或。
a^b^c^a === b^c
所以这题非常适合,一直异或,最后的值就是那个单身
三、AC 代码:
Hash的方法
/** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { let obj = {} nums.forEach(item=>{ item in obj ? delete obj[item]:(obj[item]=null) }) return Object.keys(obj)[0] };
异或的方法:
/** * @param {number[]} nums * @return {number} */ var singleNumber = function(nums) { return nums.reduce((acc,cur)=>acc^cur)) };
四、总结:
- 快速取值用hash对象,且hash对象可以快速判断某key有没有