494，位运算解只出现一次的数字

Original 山大王wld 数据结构和算法 2022-05-19

收录于合集 #算法图文分析 161个

By letting go of something, your arms are free to grab hold of something else.

学会放手，才能获得更多。

问题描述

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

说明：

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

示例 1:

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

示例 2：

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

位运算解决

这题说的是只有一个数出现了一次，其他数字都出现了2次，让我们求这个只出现一次的数字。这题使用位运算是最容易解决的，关于位运算有下面几个规律

1^1=0;

1^0=1;

0^1=1;

0^0=0;

也就说0和1异或的时候相同的异或结果为0，不同的异或结果为1，根据上面的规律我们得到

a^a=0；自己和自己异或等于0

a^0=a；任何数字和0异或还等于他自己

a^b^c=a^c^b；异或运算具有交换律

有了这3个规律，这题就很容易解了，我们只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字。来看下代码

1public int singleNumber(int nums[]) {
2    int result = 0;
3    for (int i = 0; i < nums.length; i++)
4        result ^= nums[i];
5    return result;
6}

使用集合Set解决

这个应该是最容易想到的，我们遍历数组中的元素，然后在一个个添加到集合Set中，如果添加失败，说明以前添加过，就把他给移除掉。当我们把数组中的所有元素都遍历完的时候，集合Set中只会有一个元素，这个就是我们要求的值。

 1public int singleNumber(int[] nums) {
 2    Set<Integer> set = new HashSet<>();
 3    for (int num : nums) {
 4        if (!set.add(num)) {
 5            //如果添加失败，说明这个值
 6            //在集合Set中存在，我们要
 7            //把他给移除掉
 8            set.remove(num);
 9        }
10    }
11    //最终集合Set中只有一个元素，我们直接返回
12    return (int) set.toArray()[0];
13}