leetcode_268.missing number

佚名 6年前 (2019-04-26) 随笔 1663人围观抢沙发百度已收录

给定一个数组nums，其中包含0--n中的n个数，找到数组中没有出现的那个数。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解法一：cyclic swapping algorithm

class Solution
{
public:
    int missingNumber(vector<int>& nums)
    {
        nums.push_back(-1);
        int len=nums.size();
        for(int i=0;i<len;i++)
        {
            while(nums[i]>=0 && nums[i]!=i)
                swap(nums[i], nums[nums[i]]);
        }
        for(int i=0;i<=len;i++)
            if(nums[i]==-1)
                return i;
        return -1;
    }
};

解法二：用(1+n)*n/2减掉数组中所有数，就是没有出现的那个数。

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

解法三：使用异或运算符，a^b^b=a。

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