只出现一次的数字
原创
题目
难度级别：简单
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1] 输出: 1
示例 2:
输入: [4,1,2,1,2] 输出: 4
解题思路
法一
倒叙遍历相等则删除，时间复杂度为O(n^2)，不满足线性时间复杂度O(n)，而且这个方法也太慢了。。。执行用时如下图。
const singleNumber = function(nums) {
for(let i = nums.length; i >= 0; i--) {
for(let j = i - 1; j >= 0; j--) {
if (nums[i] === nums[j]) {
nums.splice(i, 1) && nums.splice(j, 1)
continue;
}
}
}
return nums[0]
};法二：位运算
上图方法太慢，考虑到线性时间复杂度和常数空间复杂度，使用位运算，因为它满足交换律和结合律
即： a | a = 0，a | 1 = a , a | 1 | a = a | a | 1
再看一下执行时间，快了好多。。
const singleNumber = function(nums) {
for(let i = 1; i < nums.length; i++)
nums[0] ^= nums[i]
return nums[0]
};来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/single-number
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
