【专知-关关的刷题日记17】Leetcode 268. Missing Number- 专知

【专知-关关的刷题日记17】Leetcode 268. Missing Number

点击上方“专知”关注获取更多AI知识!

题目

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;
    }
};