原题
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
输入： [2,2,1] 输出： 1
示例2：
输入： [4,1,2,1,2] 输出： 4
解法
思想
- 哈希集
第一次出现加到集合中，第二次出现从集合中删除，最后集合中剩下的那个元素即为只出现一次的数。 - 亦或
- 两个相同的数亦或的结果为0
- 0和n亦或的结果为n
=> 则所有数亦或的结果即为只出现一次的数。
代码
- 哈希集
class Solution {
public int singleNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int i:nums){
if(set.contains(i)) set.remove(i);
else set.add(i);
}
for(int i:nums){
if(set.contains(i)) return i;
}
return 0;
}
}
- 亦或
class Solution {
public int singleNumber(int[] nums) {
int i,res=0;
for(i=0;i<nums.length;i++){
res=res^nums[i];
}
return res;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode136-%e5%8f%aa%e5%87%ba%e7%8e%b0%e4%b8%80%e6%ac%a1%e7%9a%84%e6%95%b0%e5%ad%97/
