Leetcode41 缺失的第一个正数

41. 缺失的第一个正数

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

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

1
2
3
>输入：nums = [1,2,0]
>输出：3
>解释：范围 [1,2] 中的数字都在数组中。

示例 2：

1
2
3
>输入：nums = [3,4,-1,1]
>输出：2
>解释：1 在数组中，但 2 没有。

示例 3：

1
2
3
>输入：nums = [7,8,9,11,12]
>输出：1
>解释：最小的正数 1 没有出现。

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1

这个问题可以通过将数组中的每个数字放到它应该在的位置来解决，即 nums[i] 应该放在 nums[i-1] 的位置，相当于把原来的数组当作一个哈希表来使用，具体步骤如下：

  • 初始化：设置 max_len 为数组长度加1，这是我们需要处理的最大正整数。

  • 标记无效数字：将所有非正数或大于 n 的数字设置为0。

  • 放置数字：

    • 对于每个数字 nums[i]，如果它在范围内（1 到 max_len - 1），则将其放到正确的位置 nums[nums[i] % max_len - 1]，并加上数组的最大长度，标记这个位置的数已经出现过了。
    • 使用一个循环来重复这个过程，直到所有在范围内的数字都被放到了正确的位置。

  • 查找缺失的最小正整数：

    • 遍历数组，如果 nums[i] 小于 max_len，则 i+1 就是缺失的最小正整数。
    • 如果所有位置都填满了，那么缺失的最小正整数就是 max_len。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        max_len = n + 1

        # 初始化：设置 max_len 为数组长度加1，这是我们需要处理的最大正整数。
        # 标记无效数字：将所有非正数或大于 n 的数字设置为0。
        for i in range(n):
            if nums[i] <= 0 or nums[i] >= max_len:
                nums[i] = 0
        
        # 放置数字
        for i in range(n):
            if nums[i] % max_len != 0:
                cur = (nums[i] % max_len) - 1
                nums[cur] = (nums[cur] % max_len) + max_len

        # 查找缺失的最小正整数
        for i in range(n):
            if nums[i] < max_len:
                return i+1
        return max_len

转自leetcode小天才才

题目不难，总结一下就是利用各种标识方法（这里用的是+num_len来判断是否被标记，官方解法是使用正负号来标识哪儿个位置的元素被标记），然后最后再遍历一下哪儿个位置没有被标记，然后去除第一个没有被标识的位置