讨论/《算法面试题汇总》 - 缺失数字/
《算法面试题汇总》 - 缺失数字
共 4 个回复

1,位运算求解

题中的意思就是从数字[0,n]之间的n+1个数字少了一个,而其他的数字都存在。

如果我们把这个数组添加从0~nn+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 missingNumber(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++)
            xor ^= nums[i] ^ (i + 1);
        return xor;
    }

看一下运行结果

image.png

或者还可以这样写,原理都是一样的

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


2,求和

如果不缺那个数字的话,这个数组的所有数字可以组成一个等差数列,我们只需要根据公式求和,然后再减去数组中所有的数字即可,代码如下

    public int missingNumber(int[] nums) {
        int length = nums.length;
        int sum = (0 + length) * (length + 1) / 2;
        for (int i = 0; i < length; i++)
            sum -= nums[i];
        return sum;
    }

image.png


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

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

1

因为数组中所有数字都是独一无二的,所以将 0 - n 所有数字加起来,用total 代表,将数组中所有数字也加起来,用sum 代表,那么,total - sum 就是缺失的数字,打败了100% 的用户。

`class Solution {
public int missingNumber(int[] nums) {
int total = 0;
int sum = 0;

    for (int i = 0; i < nums.length; i ++){
        total += i;
        sum += nums[i];
    }

    total += nums.length;
    
    return total - sum;
}

}`

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int sum = (1 + n) * (n) / 2;
        for (int i : nums) {
            sum -= i;
        }

        return sum;
    }
}

按位异或,相同的两个数异或后为0,最后剩下的那个数就是缺失的数字。
2 ^ 2 = 0,
2 ^ 2 ^ 3 = 3

var missingNumber = function (nums) {
    const len = nums.length
    let ret = 0
    for (let i = 0; i < len; i++) {
        ret = ret ^ i ^ nums[i]
    }
    // 右边界len
    return ret ^ len

};