找出缺失的数字

最近在看算法题，其中比较有意思的一道：

问题描述：给定一个有n个不同数字，是0-n，其中有一个数字是缺少的，找出这个数字，最好是线性的时间结构，不使用额外的内存空间

思路1.算出这n个数字之和，与0-n这n+1个数字之和进行比较，缺少的数字就是2个数字之差

思路2.对数组进行排序，然后使用二分法进行查找

思路3.首先我们知道，n^m^n = m 那么，(0^1^2^3...^n) ^ (0^1^2^3...^n) 前半部分为0-n的n+1个数字，后半部分为题中给出的数组，这样就可以求出那个单独的数字

以下为代码的实现，供大家参考，着重理解解题的思路

 1 package com.xiong.test;
 2 
 3 import java.util.Arrays;
 4 
 5 public class MissingNum {
 6     
 7     /***
 8      * Given an array containing n distinct numbers taken from 0, 1, 2, ..., n,
 9      *  find the one that is missing from the array.
10      *  Input: [3,0,1]
11      *  Output: 2
12      *  
13      *  思路1.算出数组的和，可以找出缺少的那个
14      *  思路2.排序后二分法查找
15      *  思路3.与法
16      */
17     //first
18     public static int missingNumber(int[] nums) {
19         Arrays.sort(nums);
20         int low = 0, high = nums.length;
21         while (low <= high) {
22             int mid = (low + high)/2;
23             if (nums[mid] > mid) {
24                 high = mid - 1;
25             } else {
26                 low = mid + 1;
27             }
28         }
29         return low;
30     }
31     //和法
32     public static int missingNumber2(int[] nums) {
33         int res = (nums.length) * (nums.length + 1)/2;
34         int sum = 0;
35         for (int i = 0; i < nums.length; i++) {
36             sum += nums[i];
37         }
38         return res - sum;
39     }
40     //与法
41     public static int missingNumber3(int[] nums) {
42         int res = nums.length;
43         for (int i = 0; i < nums.length; i++) {
44             res ^= nums[i];
45             res ^= i;
46         }
47         return res;
48     }
49     
50     public static void main(String[] args) {
51         int[] nums = {9,6,4,2,8,5,7,0,1};
52         System.out.println(missingNumber3(nums));
53         System.out.println(missingNumber2(nums));
54         System.out.println(missingNumber(nums));
55     }
56 
57 }

如果有什么问题希望大家批评指正，谢谢