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

使用异或,相同的数字异或得0,最后只剩下一个数字。

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

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主页查看更多的详细题解

19

一个数字与0异或等于本身,一个数字与本身异或等于0;把所有数字进行异或就能得到结果。

19

解题思路

结合异或位运算的两个重要性质
1、对于任意数a,与0异或, 结果等于 a
2、对于任意数a, 与其本身异或,结果等于0

所以可把数组中所有元素异或,出现偶数次的数会变为0,剩下的值就是出现奇数次数的数。

代码

func singleNumber(nums []int) int {
    for i:=1;i<len(nums);i++{
        nums[0]^=nums[i]
    }
    return nums[0]
}
4

刚开始没看懂,后来想到异或运算具有交换律,所以把所有数字异或到一起结果就是那个只出现了一次的数字

2

1.首先明确一个数和0异或等于这个数本身,两个相同的数进行异或等于0
2.将数组的第一个数与0进行异或产生数n,然后将数组的第二个数与n进行异或,依次类推,最终将数组中的数全部进行了异或
3.将十进制的数转换为计算机中的二进制的数进行运算会发现,即使相同的两个数不在相邻的位置,只要出现过两个相同的数,依旧会异或成0,最终所有出现两次的数都成为了0,就是0和出现一次的数进行异或,返回那个数,就返回了数组中只出现了一次的那个数

3

最精简

eval(nums.join('^'))
1

思路:采用异或,数组内所有元素异或

  1. 归零律:a ^ a = 0
  2. 恒等律:a ^ 0 = a
  3. 交换律:a ^ b = b ^ a
  4. 结合律:a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
  5. 自反:a ^ b ^ a = b.
  6. d = a ^ b ^ c 可以推出 a = d ^ b ^ c.
    若x是二进制数0101,y是二进制数1011;则x^y=1110
    [4,1,2,1,2] 则 4^1^2^1^2=4 故思路为该数组内所有元素异或最后的结果则为目标元素
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < nums.length; i++)
            result =result^nums[i];
        return result;
    }
}

1

不符合题目输入要求,2出现了3次

1

对,也就是运用了异或的归零律、恒等律和结合律的知识。

2