讨论/《算法面试题汇总》 - 只出现一次的数字/
《算法面试题汇总》 - 只出现一次的数字
共 1 个回复

1,位运算解决

这题说的是只有一个数出现了一次,其他数字都出现了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个规律,这题就很容易解了,我们只需要把所有的数字都异或一遍,最终的结果就是我们要求的那个数字。来看下代码

public int singleNumber(int nums[]) {
    int result = 0;
    for (int i = 0; i < nums.length; i++)
        result ^= nums[i];
    return result;
}

看下运行结果

image.png


2,使用集合Set解决

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

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


我把部分算法题整理成了PDF文档,截止目前总共有900多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

2