极客算法

41. 缺失的第一个正数(First Missing Positive)

2020-08-31

该题还是挺难的,我们从第一个答案开始,一步一步过渡到最终答案

41. First Missing Positive

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

示例 1:

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

示例 2:

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

示例 3:

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

  提示:

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

哈希(字典/集合)

空间复杂度O(N)

  1. 统计一下数组元素是否出现
  2. 按自然数查找缺失的数字
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        n = len(nums)
        seen = set()
        
        for num in nums:
            if num not in seen:
                seen.add(num)
            
        for i in range(1, n + 1):
            if i not in seen:
                return i
            
        return n + 1

哈希(数组)

空间复杂度O(N)

思路与上一个相同, 只是使用数组作为集合, 哈希函数为index = num - 1

  1. 统计一下数组元素(1 <= num <= n)是否出现
  2. 按自然数查找缺失的数字
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        n = len(nums)
        seen = [False for i in range(n)]
        
        for num in nums:
            if 1 <= num <= n:
                seen[num - 1] = True
                
        for i in range(1, n + 1):
            if not seen[i - 1]:
                return i
            
        return n + 1

数组

空间复杂度O(N)

  1. 第i个位置存储num, 且i = num - 1
  2. 自然顺序,遍历数组遇到不相等的,就是答案。如果都不相等, 答案n + 1
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        n = len(nums)
        seen = [False for i in range(n)]
        
        for num in nums:
            if 1 <= num <= n:
                seen[num - 1] = num
                
        for i in range(1, n + 1):
            if i != seen[i - 1]:
                return i
            
        return n + 1

解题

空间复杂度O(1), 利用原有数组,没有使用额外空间

  1. 如果1 <= num <= n, 把目标数字num移动到对应的下标下
  2. 自然顺序,遍历数组遇到不相等的,就是答案。如果都不相等, 答案n + 1
class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        
        n = len(nums)
        
        i = 0
        while i < n:
            j = nums[i] - 1
            
            if 0 <= j < n and nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
            else:
                i += 1
                
        for i in range(1, n + 1):
            if i != nums[i - 1]:
                return i
            
        return n + 1

–End–


相关推荐

评论

内容: