Missing-Number

发表于 | 更新于：

LeetCode#268 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

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

Example 2

1
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?

解题思路

  emmmm，很没有意思的一道题。题目要求是找到从0-N的数组中缺失的那一个数字（这些数字乱序排列且唯一），我没有试排序的方法而是用另一种思路。我们将0-N加起来，再将数组中的元素加起来，两者相减之后就是缺少的那个元素。

解题代码【.CPP】

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int missingNumber(vector<int> &nums) {
        int sum1 = 0, sum2 = 0;
        for (int i = 0; i < nums.size(); ++i) {
            sum1 += i;
            sum2 += nums[i];
        }
        sum1 += nums.size();
        return sum1 - sum2;
    }
};
0%