leetcode136-只出现一次的数字

原题

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

输入: [2,2,1] 输出: 1

示例2:

输入: [4,1,2,1,2] 输出: 4

解法

思想

  1. 哈希集
    第一次出现加到集合中,第二次出现从集合中删除,最后集合中剩下的那个元素即为只出现一次的数。
  2. 亦或
    • 两个相同的数亦或的结果为0
    • 0和n亦或的结果为n
      => 则所有数亦或的结果即为只出现一次的数。

代码

  1. 哈希集
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;
    }
}
  1. 亦或
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/