LeetCode

LeetCode 268. Missing Number 题解

查阅更多的题解,请点击

Problem

268. Missing Number

Solution

题目要求算法O(n) time, O(1) space,那么可以考虑in-place的算法:

  • 注意n个数,数的取值在[0,n]之间且唯一,可以遍历一遍数组,将值与索引对应,即使得处理之后的数组满足nums[i]=i:
    • 若所缺失的数为n,则数组所有元素均满足nums[i]=i;
    • 否则必然存在nums[i]不等于i,所求数即为i
  • 考虑异或操作有以下性质,考虑用异或操作完成该问题:
    • a ^ b ^ b=a
    • 满足交换律,即:a ^ b ^ c ^ b ^ c = a ^ b ^ b ^ c ^ c=a

GitHub传送门

in-place

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

位运算:

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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注