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?

分析

给定包含}中的n个，找出缺失元素。

方法一：排序法 时间O(nlogn) 空间O(1)
现将序列元素排序，然后一次遍历；

方法二：
时间O(n) 空间O(1)
由题意，大小为计算出来的，所以我们遍历一遍记录最大、最小和数组和，用期望数组和减去实际数组和，就是缺失的整数。

AC代码

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        if (nums.empty())
            return 0;

        sort(nums.begin(), nums.end());

        for (unsigned i = 0; i < nums.size(); ++i)
        {
            if (nums[i] != i)
                return i;
        }//for
        return nums.size();
    }
};

GitHub测试程序源码