[每日LeetCode] 268. Missing Number

  |   0 评论   |   558 浏览

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

评论

发表评论