# [LeetCode 41] 用原数组保存信息

首先这题一个很明显的性质:缺少的那个整数一定在[1, n + 1](n为nums的长度)之间。为什么?假设这个数组是从1开始,然后依次递增并且不重复,全部填充时数组正好是[1, n],此时缺少的整数就是n + 1;然后前面替换掉哪个数,哪个数就是缺少的,在[1, n]之间。

所以,可以想到一个很自然的解法,用一个数组来记录[1, n]之间哪个数已经出现过了,没出现的那个就是缺少的;如果全都出现了,那就是缺少了n + 1。这个解法我认为比哈希表还要自然:

int firstMissingPositive(vector<int> &nums)
{
    int length = nums.size();
    vector<bool> lookup(length, false);
    for (int &n : nums)
    {
        if (1 <= n && n <= length)
        {
            lookup[n] = true;
        }
    }
    for (int i = 1; i <= length; ++i)
    {
        if (!lookup[i])
        {
            return i;
        }
    }
    return length + 1;
}

虽然这个方法可以满足O(n)的时间复杂度,但题目要求是空间复杂度O(1),这个方法的空间复杂度是O(n),还需要进一步优化。

仔细想想,这个方法的本质是什么,记录[1, n]之间已经出现过的数。目前我们是开了个新数组,但是这个数组其实可以不用开,我们完全可以在原数组上记录,只需要用符号来表明这个位置对应的数是否已经出现过即可。如果当前位置的数为正,说明当前位置对应的数没出现过;反之则是已经出现过。当然,这个可能会和原有的负数冲突,所以就需要把原有的负数变成不影响结果的正数(并且负数本身就不影响结果):

int firstMissingPositive(vector<int> &nums)
{
    int length = nums.size();
    for (int &n : nums)
    {
        if (n <= 0)
        {
            n = length + 1;
        }
    }
    for (int i = 0; i < length; ++i)
    {
        int index = abs(nums[i]) - 1;
        if (index < length && nums[index] > 0)
        {
            nums[index] *= -1;
        }
    }
    for (int i = 0; i < length; ++i)
    {
        if (nums[i] > 0)
        {
            return i + 1;
        }
    }
    return length + 1;
}

事实上,用原数组保存信息这种思路还是比较常见的。

最后更新于: 6/27/2020, 11:15:18 AM