如何以最优方式求解非负整数数组的MEX（最小排除值）？

MEX指集合/列表中缺失的最小非负整数，典型示例：

• MEX [] = 0
• MEX [1,2,3,10000] = 0
• MEX [0,1,3,4] = 2
• MEX [0,1,2,3] = 4

你之前采用的排序+索引对比法时间复杂度为O(nlogn)，这里提供两种时间复杂度O(n)的更优解法：

方法一：哈希集合法 #

思路 #

将列表所有元素存入哈希集合，从0开始依次检查每个非负整数是否存在于集合中，第一个不存在的数就是MEX。由于列表长度为n时，MEX的最大值为n（当0到n-1全部存在时），因此最多只需检查到n即可。

代码实现（Python） #

def find_mex(nums):
    num_set = set(nums)
    mex = 0
    while mex in num_set:
        mex += 1
    return mex

复杂度分析 #

• 时间：O(n)，存入集合的遍历是线性时间，查找MEX的循环最多执行n+1次，总时间仍为线性。
• 空间：O(n)，需要额外存储哈希集合。

方法二：原地置换法（空间优化版） #

思路 #

利用数组索引与MEX的对应关系：若MEX为m，则0到m-1必然全部存在于列表中，而m缺失。我们可以将每个满足0 ≤ x < n（n为列表长度）的元素x置换到索引x的位置，之后遍历数组，第一个索引i与对应元素nums[i]不相等的i就是MEX；若所有索引都匹配，则MEX为n。

代码实现（Python） #

def find_mex_in_place(nums):
    n = len(nums)
    for i in range(n):
        # 循环置换，直到当前位置元素匹配索引，或元素不在0~n-1范围内
        while 0 <= nums[i] < n and nums[nums[i]] != nums[i]:
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
    # 查找第一个不匹配的索引
    for i in range(n):
        if nums[i] != i:
            return i
    # 所有0~n-1都存在，返回n
    return n

复杂度分析 #

• 时间：O(n)，每个元素最多被置换一次，遍历数组也是线性时间。
• 空间：O(1)，仅使用常数额外空间（需允许修改原数组）。

注意事项 #

该方法会修改原数组，若不能改动输入列表，建议使用哈希集合法。

内容的提问来源于stack exchange，提问作者MLEPalawat