41. 缺失的第一个正数 [hard]

https://leetcode-cn.com/problems/first-missing-positive/

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]
输出: 3

示例 2:

输入: [3,4,-1,1]
输出: 2

示例 3:

输入: [7,8,9,11,12]
输出: 1

提示：

你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。

通过次数78,462 | 提交次数195,061

Second Try

2020-07-24

竟然还可以用swap数字交换实现目标，而且一轮交换竟然只用O(n)复杂度。

因为目标值只在[1, len(nums)]范围内，能留下来被考虑的也只在这个范围内。本质上并不是比较大小，而是找到对应的坐标。

容易出bug的地方:

有效的nums[i]保存的位置是nums[nums[i] - 1], 因为1保存在nums[0]。
其次是当交换的对象目标相等nums[nums[i] - 1] == nus[i]的时候，直接跳到下一步，不然就无限循环了。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 据说还可以用swap数字交换？ 反正nums[i]在[1, len(nums)]范围内都有效。
        # 这一轮交换，竟然只用O(n)复杂度。因为本质上并不是比较大小，而是找到对应的坐标。

        i, n = 0, len(nums)
        while i < n:
            if nums[i] <= 0 or nums[i] > n:  # 无效数据，跳过
                i += 1
            else:
                idx = nums[i] - 1 # 考虑位置，nums[0]保存的是1，而不是0 
                if nums[idx] == nums[i]:  # 重复了，交换无用
                    i += 1
                else:
                    nums[idx], nums[i] = nums[i], nums[idx]
        
        # 交换完毕，遍历一波看哪个位置不对劲
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1 
        return n + 1 # 最后补数 

执行用时：40 ms, 在所有 Python3 提交中击败了76.44%的用户
内存消耗：13.8 MB, 在所有 Python3 提交中击败了16.67%的用户

First Try

2020-07-24

奇怪的题目，奇怪的解法。。。

题目要求是最小的正整数，因此0和负数都可以排除掉，并且可能的数字明显在[1...len(nums)] + len(nums) + 1之间，注意并不是[0...len(nums) - 1] + len(nums)

第一轮先把负数干掉，不要影响判断。因为接下来的标记需要换为负数，才能既有标记，还保持原来的有效数字。直接把负数都取值为len(nums) + some，反正不在筛选范围内。注意0也是无效数字，因此也需要直接干掉。

第二轮进行标记，如果nums[i]在[1...len(nums)]范围内，则idx = nums[i], nums[idx] = -nums[idx]，说明idx这个位置已经有有效数字了。如果遇到nums[idx]为负数，则转化为正数，再进行相应判断即可, 也即 idx = abs(nums[i])。

第三轮检查nums中哪个位置不为负数，则这是第一个需要填充的正数。如果所有位置都是负数，说明它们都是密集排列的有效数字，直接返回len(nums) + 1即可。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 存粹靠理解题意来解题, 一点都不通用。。。
        # 有效数字是[1...len(nums)] + len(nums) + 1， 
        # 而不是[0...len(nums) - 1] + len(nums), 并且也不包含负数 

        # 把idx为负的搞掉，因为需要的只是正整数，这题目啊。。
        for i in range(len(nums)):
            if nums[i] <= 0:  # 0 也要去掉。。。
                nums[i] = len(nums) + 999 
        
        # 把在[0, len(nums)]范围内的元素位置进行标记，遇到负数的话，转正也进行标记。
        for i in range(len(nums)):
            if abs(nums[i]) > len(nums):
                continue 
            idx = abs(nums[i]) - 1  # 注意有效数字是[1...len(nums)]， 而不是[0...len(nums) - 1]
            nums[idx] = - abs(nums[idx])
        
        # 检查不为负数的地方
        for i in range(len(nums)):
            if nums[i] > 0:
                return i + 1
        return len(nums) + 1  # 最后就是n + 1了

执行用时：44 ms, 在所有 Python3 提交中击败了52.94%的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了16.67%的用户