技术教程 未出现的最小正整数 正文

未出现的最小正整数

2022-10-22,

First Missing Positive Integer

未出现的最小正整数

问题描述
给定一个未排序的整数列表，找出其中没有出现的最小的正整数，给定列表中可能包含重复的元素。要求算法是时间复杂度是O(n)，空间复杂度是O(1)。

测试样例

# Input: 
[3, 4, -1, 1, 2, 2, 5]
# Output: 
6
# 列表长度为7，列表中出现了1，2，3，4，5
# 没有出现6和7，所以第一个缺少的整数是6.

图解思路

参考代码

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
class Solution:
    # O(n) time, O(1) space.
    def firstMissPositive(self, nums):
        if not nums:
            return 1   
        for idx, num in enumerate(nums):
            # 缺失的数必定在 0 到 len(nums)之间
            while nums[idx] != idx + 1 and 0 < nums[idx] <= len(nums):
                value = nums[idx]
                if nums[idx] == nums[value-1]:
                    break
                nums[value-1], nums[idx] = nums[idx], nums[value-1]
        for idx, num in enumerate(nums):
            if idx + 1 != num:
                return idx + 1
        return len(nums) + 1
    
# Test Program
nums = [3, 4, -1, 1, 2, 2, 5]
result = Solution().firstMissPositive(nums)
print(result)
# 6

《未出现的最小正整数.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!