[每日 LeetCode] 268. Missing Number

Description:

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?

本题要求找到数组中缺少的那个数字，数组是乱序的，数组长度为 nums.size()+1，要求在 O(1)空间和 O(n)时间内完成，想到了两种思路。思路二要优于思路一。

思路一：先对数组排序，找到不应该出现在该数组位置上的元素，若所有的元素都在应有的位置上，则返回 nums.size()。

思路二：对数组求和，用应该得到的数组之和减去现有数组的和，即得到了缺少的那个数字。

C++ 代码（思路一）

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        for (int i=0; i<nums.size(); i++){
            if (nums[i] != i){
                return i;
            }
        }
        return nums.size();
    }
};

运行时间：36ms

运行内存：9.8M

C++ 代码（思路二）

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for (auto a : nums) {
            sum += a;
        }
        return 0.5 * n * (n + 1) - sum;
    }
};

运行时间：24ms

运行内存：9.7M