【专知-关关的刷题日记17】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.

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的数组,数组中存了0-n每一个数,其中有一个数字缺失了,需要我们找出来缺失的数字。要求时间复杂度为O(n),空间复杂度为O(1)。

方法1

方法1:因为数组中存的是0-n这些连续的数,只有一个数字缺失了,所以可以把数组中元素的和算出来,0-n这些连续数的和是(n-1)*n/2, 然后二者作差,就可以找出来缺失的数字了。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int sum=0;
        for(int x:nums)
            sum+=x;
        return (1+nums.size())*nums.size()/2-sum;
    }
};

方法2

方法2:采用异或的思路,本质上与方法1是一样的,上面的做法是利用n个数的和减去实际的和,异或的做法是用n个数异或的结果异或上实际的异或的结果。

0^a=a^0=a;a^b=b^a;a^a=0;

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int res=0;
        for(int i=1; i<=nums.size(); i++)
            res=res^i^nums[i-1];
        return res;
    }
};

师父根据这道题目给出的思路拓展:不适用第三个变量来交换a和b的值。方法1:采用加减法的方法:第一步:a=a+b;第二步:b=a-b;第三步:a=a-b;

方法2:采用异或的方法:第一步:a=a^b;第二步:b=a^b;第三步:a=a^b;

成功、优秀这个维度上是没有止境的,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-10-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(三十)附基础教程

BAT常见的算法面试题解析:程序员算法基础——动态规划程序员算法基础——贪心算法工作闲暇也会有在线分享,算法基础教程-。

2513
来自专栏落影的专栏

程序员进阶之算法练习(十九)

前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

3776
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

4355
来自专栏聊聊技术

原 初学数模-MATLAB Quick S

4619
来自专栏chenjx85的技术专栏

leetcode-453-Minimum Moves to Equal Array Elements

3266
来自专栏数据结构与算法

UOJ#386. 【UNR #3】鸽子固定器(链表)

如果我们按$s$排序后,我们就可以枚举$max  \ s_i$和$min \ s_i$

1101
来自专栏专知

关关的刷题日记80 – Leetcode 7. Reverse Integer

关关的刷题日记80 – Leetcode 7. Reverse Integer 题目 Given a 32-bit signed integer, revers...

3387
来自专栏aCloudDeveloper

算法导论第九章中位数和顺序统计量(选择问题)

  本章如果要归结成一个问题的话,可以归结为选择问题,比如要从一堆数中选择最大的数,或最小的数,或第几小/大的数等, 这样的问题看似很简单,似乎没有什么可研究的...

3357
来自专栏游戏杂谈

IEEE 754二进制浮点数算术标准

纳尼,不应该是0.1么,怎么变成0.09999999999999998呢?这就要从ECMAScript标准讲起了。

1312
来自专栏Albert陈凯

数据结构与算法汇总

文章作者博客微信公共账号:hadoop123(微信号为:hadoop-123),分享hadoop技术内幕,hadoop最新技术进展,发布hadoop相关职位和求...

3715

扫码关注云+社区

领取腾讯云代金券