JavaScript解LeetCode之只出现一次的元素
JavaScript解LeetCode之只出现一次的元素
刘亦枫
发布于 2020-03-19 17:26:53
发布于 2020-03-19 17:26:53
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
不使用额外空间，意思是空间复杂度是O(1)，无论数据规模多大，都可以在一次计算后找到目标。 线性时间复杂度，就是时间复杂度为线性阶O(n)。本题的意思是用的时间越少越好。
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
答案解读
1.
var singleNumber = function(nums) {
var res = nums[0];
for(var i=1;i<nums.length;i++){
res^=nums[i];
}
return res;
};^是异或的意思，res^=nums[i]等价于res = res ^ nums[i]
执行用时 : 60 ms
内存消耗 : 35.3 MB
2.
var singleNumber = function(nums) {
let map = new Map();
for(let i=0;i<nums.length;i++){
if(map.has(nums[i])){
map.set(nums[i], map.get(nums[i])+1);
}
else{
map.set(nums[i], 1);
}
}
for(let key of map.keys()){
if(map.get(key)==1){
return key;
}
}
return -1;
};myMap.has(key) 用来检测是否存在指定元素的键值.
执行用时 : 68 ms
内存消耗 : 37.8 MB
3.
const singleNumber = nums => nums.reduce((prev, cur) => prev ^ cur);进行位异或运算
执行用时 : 64 ms
内存消耗 : 35.3 MB
异或
异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为： a⊕b = (¬a ∧ b) ∨ (a ∧¬b)
^：与（x^y）两二进制上下比较只有位不相等时才取1，否则取零
14^15 (14 二进制 1110
15 二进制 1111
^与的结果 0001 ----》结果1)本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录