每天一道LeetCode >> 找出数组中缺失的那个数（位运算）

原题的地址：https://leetcode.com/problems/missing-number/description/

题目：Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
示例：Input: [3,0,1] Output: 2

解题思路：本思路是集中于用位运算进行求解。

• 由于该数组所具有的性质，先设置一个起始量res，不断地进行和下标值以及元素值进行异或操作：
  int ret = 0; for (int i = 0; i < nums.length; i++) { ret = ret ^ i ^ nums[i]; }

由于除了一个缺失的数字，剩下的都是连续的并且在0~n的范围内，数组的下标是0到n-1的范围，因此出现的下标和元素值在相同的时候都会被异或清除掉，如下图所示：
就剩下最大的元素数值，因为我们知道在连续的数值内缺失的那个值肯定不能是最大值和最小值，所以最后剩下的那个就是最大值和余下的下标值（缺失的那个数值）的异或。

• 最后将得到的异或值再和数组的长度也就是数值的最大值再次进行异或，得到的结果就是那个缺失值。
  ret ^ nums.length

整个代码：

	public static int missingNumber(int[] nums) {
	    int ret = 0;
	    for (int i = 0; i < nums.length; i++) { 
	    	ret = ret ^ i ^ nums[i];
	    }
	    return ret ^ nums.length;
	}
	public static void main(String[] args) {
		int[] nums = {3, 0, 1};
		System.out.print("缺失的那个数值为：");
		System.out.println(missingNumber(nums));
	}

输出结果为：