本文共 1951 字，大约阅读时间需要 6 分钟。

题目大意

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 … n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]

输出: 2

示例 2:

输入: [9,6,4,2,3,5,7,0,1]

输出: 8

说明:

解法一：加总，求差

class Solution:    def missingNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        n=len(nums)        res=n*(n+1)/2-sum(nums)        return int(res)

解法二：先排序，序号与元素值不相等的为缺失的数字

class Solution(object):    def missingNumber(self, nums):        """        :type nums: List[int]        :rtype: int        """        nums.sort()        for i in range(len(nums)):            if i != nums[i]:                return i        else:            return i+1

以下是Java版本：

题目要求很简单，一个数组包含了从0到n个不同的数字，但是其中缺少了一个数字，找出这个数字。

比如：[0, 1, 3]这个数组，就缺少了2这个数字。

思路1：0-n求和，再减去数组元素的总和，即为缺失元素。 思路2：亦或操作。两个相同的数亦或结果为0，一个不为0的数与0亦或，其值为本身。

方法一：最直观的一个方法是用等差数列的求和公式求出0到n之间所有的数字之和，然后再遍历数组算出给定数字的累积和，然后做减法，差值就是丢失的那个数字。

1.	public class Solution {2.	    public int missingNumber(int[] nums) {3.	        int sum = (int)((nums.length + 1) / 2.0 * nums.length);4.	        for (int n : nums) {5.	            sum -= n;6.	        }7.	    return sum;8.	    }9.	}

这里由于担心数组会非常大，和会超过int的上限，所以在此并没有求和，而是两个数组的每一个数求差。不过，总体思路还是一致的，完美解决。

1.	public class Solution{2.	     public int missingNumber(int[] nums) {  3.	        int ret = nums.length;  4.	        for (int i = 0; i < nums.length; i++) {  5.	            ret += (i - nums[i]);  6.	        }  7.	        return ret;  8.	    }  9.	}

方法二：使用位操作Bit Manipulation来解的，用到了异或操作的特性，主要就是利用 0 ^ a = a， 以及 a ^ b ^ a = b。思路是既然0到n之间少了一个数，我们将这个少了一个数的数组合0到n之间完整的数组异或一下，那么相同的数字都变为0了，剩下的就是少了的那个数字了。

1.	public class Solution{    2.	     public int missingNumber(int[] nums) {3.	        if(nums == null || nums.length == 0) {4.	            return 0;5.	        }6.	        int res = nums.length;    // nums.length = n7.	        for(int i = 0; i < nums.length; i++) {8.	            res ^= i;9.	            res ^= nums[i];10.	        }11.	        return res;12.	    }13.	}

转载地址：http://gpuvi.baihongyu.com/