Missing Number

Given an array containingndistinct numbers taken from0, 1, 2, ..., n, find the one that is missing from the array.

For example, Givennums=[0, 1, 3]return2.

题目大意：

给定一个包含从0, 1, 2, ..., n, 选出的n个不同数字的数组，从中找出数组中缺失的那一个数。

例如， 给定 nums = [0, 1, 3] 返回2。

解题思路：

解法I：等差数列前n项和 - 数组之和

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

解法II：位运算（异或运算）

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = len(nums)                      
        for i in xrange(len(nums)):
            result ^= i ^ nums[i] 
        return result

注意 result初始化为len(nums)。

解法III：binary search(Java)

public int missingNumber(int[] nums) { //binary search
    Arrays.sort(nums);
    int left = 0, right = nums.length, mid= (left + right)/2;
    while(left<right){
        mid = (left + right)/2;
        if(nums[mid]>mid) right = mid;
        else left = mid+1;
    }
    return left;
}

follow up:

If the array is in order, I preferBinary Searchmethod. Otherwise, theXORmethod is better.