136. 只出现一次的数字
题目描述（难度：简单）
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度
示例1:
输入: [2,2,1] 输出: 1示例2:
输入: [4,1,2,1,2] 输出: 4
思路1:
- 哈希方法
代码1
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = (nums) => {
let hash = {};
for(let i =0;i<nums.length;i++){
if(hash[nums[i]]){
delete hash[nums[i]]
}else{
hash[nums[i]] = 1;
}
}
return Object.keys(hash)[0]
};思路 2
- 先排序，再遍历判断当前项和前一项，后一项是否相等。如果不相等，则就是当前项
代码2
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = (nums) => {
nums = nums.sort();
for(let i = 0;i<nums.length;i++){
if(nums[i] !== nums[i-1] && nums[i] !== nums[i+1]){
return nums[i]
}
}
};思路 3
- 将数组遍历，并通过过滤的方法，将值相同的数归集为数组的一个元素，由于除了一个元素，其他元素都会出现两次，所有只要找到过滤的集合的长度为1的那个集合，该集合第一个元素即是该元素。
- 1.遍历数组，由于需要返回值，这里使用map方法
- 2.使用过滤函数，过滤数组中值与当前遍历的元素的值相同的元素
- 3.现在得到了一个存在多个集合的数组，而数组中唯一值的那个元素的集合肯定值存在它自己
- 4.查询这个集合中长度只有1的集合，再取这个集合的第一个元素，即是只出现一次的数字
代码 3
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = (nums) => {
const singleNum = nums.map(item => nums.filter(v => v === item))
return singleNum.find(item => item.length === 1)[0]
};复杂度分析
- 时间复杂度：O(n^2).使用了 map 和 filter，嵌套遍历;
- 空间复杂度：O(n).map方法创建了一个长度为的数组，占用了大小的空间。
思路 4
- 异或运算符可以将两个数字比较，由于有一个数只出现了一次，其他数皆出现了两次，类似乘法法则无论先后顺序，最后相同的数都会异或成0，唯一出现的数与0异或就会得到其本身，该方法是最优解，直接通过比较的方式即可得到只出现一次的数字。
- 1.将数组的一个元素与下一个元素做异或比较，直接使用reduce方法
- 2.两两异或最后与所有元素都不相同，最后返回的值即是只出现一次的数字。
代码 4
/**
* @param {number[]} nums
* @return {number}
*/
const singleNumber = (nums) => {
return nums.reduce((cur,pre) => cur ^ pre)
};复杂度分析
- 时间复杂度：O(n)。仅用 reduce 方法遍历，一层遍历
- 空间复杂度：O(1)。空间复杂度为常量，占用空间没有随数据量 的大小发生改变
