LeetCode(Others)Missing Number

Missing Number

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

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

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

思路：能想到的一个方法是先对输入数组做排序，判断排序后的元素，如果第一个数字不为0，就说明少了0。如果末尾数字不为n，就说明少了n。如果排序后的数组中存在相邻两个数字的差值为2，说明缺失的数就是这两个数中间的那个数字。

代码如下：

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int len=nums.length;
        if(len==0){
            return 0;
        }
        if(len==1){
            if(nums[0]==0){
                return 1;
            }
            if(nums[0]==1){
                return 0;
            }
        }
        int result=0;
        int count=0;
        for(int i=0;i+1<len;i++){
            if(nums[i+1]-nums[i]==2){
                result=nums[i]+1;
                count++;
                return result;
            }
        }
        if(count==0){
            if(nums[0]!=0){
                result=0;
            }
            if(nums[len-1]==len-1){
                result=len;
            }
        }
        return result;
    }
}