关关的刷题日记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：因为数组中存的是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：采用异或的思路，本质上与方法1是一样的，上面的做法是利用n个数的和减去实际的和，异或的做法是用n个数异或的结果异或上实际的异或的结果。 0a=a0=a; ab=ba; aa=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=ab; 第二步：b=ab; 第三步：a=ab;

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。