271最大化未出现自然数问题

题解

题目要求在一个长度为 n 的数组中，找出最大的未出现的自然数。具体来说，找到最小的正整数 m，使得 m 没有出现在数组中。

解题思路

1. 计数元素频次：

   使用 Counter 统计数组中每个元素出现的次数。这样可以快速判断某个数字是否存在于数组中。

2. 遍历寻找未出现的自然数：

   从 0 开始，依次检查每个数字 i 是否存在于数组中（即 cnt[i] > 0）。

   • 如果存在，则继续检查下一个数。由于操作可以把i变成更大的数字，因此可以把多余的i的个数用变量f记录下来。
   • 如果不存在，那么查看是否还有多余的更小的数字变成当前的数字。如果有则把f的计数减去1,如果没有则返回当前的 i 作为结果。

3. 返回结果：

   如果所有 0 到 n-1 的数字都存在，则返回 n。

代码

from collections import Counter

def solution(n: int, a: list) -> int:
    cnt = Counter(a)
    f = 0
    for i in range(n):
        if cnt[i] == 0:
            if f > 0:
                f -= 1
            else:
                return i
        else:
            f += cnt[i] - 1
    return n

if __name__ == '__main__':
    print(solution(5, [5, 0, 0, 2, 2]) == 4)
    print(solution(6, [1, 0, 3, 4, 4, 5]) == 2)
    print(solution(4, [0, 1, 2, 3]) == 4)

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组长度，用于统计元素频次和遍历查找。
• 空间复杂度：O(n)，用于存储元素频次。