题目

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,

Given nums = [0, 1, 3] return 2.

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

 

思路一：先排序输入的数组，然后从0开始逐一检查，发现数组中"位置数"和"数值"不一致的时候，就返回结果

 

代码：

public static int missingNumber(int[] nums) {           if(nums == null || nums.length == 0){            return 0;        }                        for(int i =0;i
     
       nums[j]){                    int temp = nums[i];                    nums[i] = nums[j];                    nums[j] = temp;                }            }        }                int i = 0;        for(i = 0;i
      
        i){                return i;            }        }                return i;    }
      
     

 

结果分析：在大测试数据的时候超时，主要原因为：冒泡排序的时候采用了循环嵌套。同时发现题目中要求使用线性的时间复杂度，同时也不能用额外的存储空间

修改代码如下：

public static int missingNumber(int[] nums) {           if(nums == null || nums.length == 0){            return 0;        }        Arrays.sort(nums);                int i = 0;        for(i = 0;i
     
       i){                return i;            }        }                return i;    }
     

 

网上高手的思路一：计算从0到n+1的和，再计算数组的和， 两个相减即为缺失的数。同时注意比较第一个数是否缺失

 

代码：

public static int missingNumber(int[] nums) {           if(nums == null || nums.length == 0){            return 0;        }                int intSumArray = 0;        boolean bHas0 = false;        for(int i =0; i< nums.length;i++){            if(nums[i] == 0){                bHas0 = true;            }            intSumArray += nums[i];        }                if(!bHas0){            return 0;        }                int intSum = (0+nums.length)*(nums.length+1)/2;                return intSum-intSumArray;    }

 

网上高手的思路二：根据异或的特性，对于一个数，异或自己是0，异或0是自己。

                           所以我们循环数组，每次异或循环次数（相当于从0到n异或一遍[异或0是自己]）再异或数组的内容（相当于异或自己[异或自己是0]）

                           最后剩余的数就是缺失的数

 

public static int missingNumber(int[] nums) {           if(nums == null || nums.length == 0){            return 0;        }                int intXORResult = 0;        boolean bHas0 = false;        for(int i = 0; i< nums.length;i++){            if(nums[i] == 0){                bHas0 = true;            }                        intXORResult = intXORResult ^ nums[i] ^ i;        }                        if(!bHas0){            return 0;        }                intXORResult = intXORResult ^ (nums.length);  //补充尚未异或的最后一位，对应最后一个数缺失的情况                return intXORResult;    }