题目
给你一个整数数组 nums ,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
解法1:哈希表
遍历一遍,哈希表存储元素次数;再遍历哈希表,找出只出现一次的元素
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], 1)
}else {
map.set(nums[i], map.get(nums[i]) + 1)
}
}
for(let [key, value] of map) {
if(value == 1) return key
}
};
- 空间复杂度: O( (n-1)/3 + 1 ) => O(n)
- 时间复杂度: O(n)
解法2:排序,遍历判断没有相邻重复的值
先对原数组从小到大排序,如果相邻两个数相等,说明它不是要的数,直接跳到当前位的后三位数继续判断,直到找到结果为止
var singleNumber = function(nums) {
nums.sort((a, b) => a -b )
console.log(nums)
let len = nums.length
let i = 0
while(i!==len-1) {
if(nums[i] === nums[i+1]) i += 3
else return nums[i]
}
return nums[len - 1]
};
- 空间复杂度: O(1)
- 时间复杂度: 不考虑排序操作的话,O(n);考虑排序的话,一般O(nlogn)
解法3:数学求和与差值方式
- 使用set的方式,对原数组去重
- 将去重后的的所有数求和setSum
- 将原数组所有数求和allSum
- 因为除了那单个数x,其他数都出现3次,所以 3* setSum = allSum + x*2
- 利用这个公式:x = (setSum*3 - allSum) /2即可得出结果
var singleNumber = function(nums) {
let set = new Set(nums)
function sum(arr) {
return arr.reduce((cur,val) => cur + val)
}
const setSum = sum([...set])
const allSum = sum(nums)
return (setSum*3 - allSum) / 2
};
- 空间复杂度: O(n)
- 时间复杂度: O(n)
解法4:位运算
遍历所有数的二进制值,比如第i位,将所有数的第i位的二进制位数相加,如果对3求模不为0,则代表那单个数这位上的二进制不为0,补1
对每一位二进制都做这个处理,最后得到的结果就是那个单个数。
- 求某个数的第i位的二进制,右移i位,再与1相与:x >> i & 1
- 将第i位的最终结果保存到结果,1左移i位,再与之前结果相或: 1 << i | res
复杂度:
- 空间复杂度: O(1)
- 时间复杂度: O(32n) => O(n)
var singleNumber = function(nums) {
let res = 0;
// i用来记录当前的二进制位数,从最后一位开始
for(let i = 0; i < 32; i++) {
let count = 0; // 用于记录所有数的当前位二进制的和
// j用来记录当前遍历到数
for(let j = 0; j < nums.length; j++) {
// 当前位右移i位,再与1相与,可以得到第i位上的二进制数
if(nums[j] >> i & 1) {
count++;
}
}
// 和对3求模,得到的就是那个单个数第i位的二进制数
if(count % 3 !== 0) {
// res为之前的数,1是用来保证
res = res | (1 << i)
}
}
return res;
};
网友评论