【面试题】缺失的第一个整数

缺失的第一个整数

仅供学习，如果有错误请指正

本文实现的代码时间复杂度是 O(n log n)，不满足题目要求

一、问题描述

排序的时间复杂度通常是 O(n log n)，但我们可以采用一种原地排序算法（如快速排序），在最坏情况下仍保持 O(n log n) 的时间复杂度。

二、解题思路

2.1 排序

首先对数组进行排序。这将允许我们线性地扫描数组以找到缺失的最小正整数。排序的时间复杂度通常是 O(n log n)，但我们可以采用一种原地排序算法（如快速排序），在最坏情况下仍保持 O(n log n) 的时间复杂度。

2.2 填充

遍历排序后的数组，对于每个索引 i，如果 nums[i] 不等于 i + 1，则返回 i + 1 作为结果。这是因为排序后的数组中，索引 i 应该包含的值是 i + 1。如果实际值不等于期望值，说明 i + 1 没有出现在数组中。

2.3 特殊情况

如果数组中所有元素都满足 nums[i] == i + 1，那么最小的未出现的正整数将是数组长度加一。

三、Python代码

def firstMissingPositive(nums):
    # 原地排序
    nums.sort()

    # 遍历排序后的数组
    missing_positive = 1
    for i in range(len(nums)):
        # 如果当前元素不等于其索引加1
        if nums[i] < 1:
            continue

        if nums[i] != missing_positive:
            # 返回当前索引加1
            return missing_positive
        missing_positive = missing_positive + 1

    return missing_positive