LeetCode 268 Missing Number(丢失的数字)

  1. 云栖社区>
  2. 博客>
  3. 正文

LeetCode 268 Missing Number(丢失的数字)

nomasp 2016-02-29 22:27:09 浏览355
展开阅读全文
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/50768898

翻译

给定一个包含从0,1,2...,n中取出来的互不相同的数字,从数组中找出一个丢失的数字。

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

备注:
你的算法应该运行在线性时间复杂度下。你可以只用常量空间复杂度来实现它吗?

原文

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?

分析

因为数组可以是非常非常大,其大小并不固定,所以哈希表应该是没用了。

中间省略了一大段的思考过程,并且先去做了下面这道题,回到这道题的时候忽然有了思路。

LeetCode 319 Bulb Switcher(灯泡切换)(从规律中发现算法……)

比如说,从零到32146的数组中,丢失的数字是4687。

我们可以计算出从0到32146的所有数字的总和是:

expectedSum:516666585

我们还可以计算出从0到32146并丢掉4687的所有数字的总和是:

actualSum:516661898

对,没错,就是这样……

代码如下:

代码

int missingNumber(vector<int>& nums) {
    int expectedSum = 0, actualSum = 0;
    for (int i = 1; i <= nums.size(); ++i) {
        expectedSum += i;
    }
    for (int i = 0; i < nums.size(); ++i) {
        actualSum += nums[i];
    }
    return expectedSum - actualSum;
}

网友评论

登录后评论
0/500
评论
nomasp
+ 关注