【数据结构和算法】位运算和求和两种方式解决

1，位运算求解

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

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

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

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

2，求和

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

    public int solve(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;
    }

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

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解