如何计算输入整数未使用数字组成的最小合法数？

核心逻辑 #

要生成未使用数字组成的最小合法数，关键在于优先使用小数字，但必须避免以0开头，具体步骤如下：

• 提取已用数字：将输入整数转为字符串集合，快速判断哪些数字被占用。
• 筛选并排序未使用数字：遍历0-9，收集未被使用的数字并按升序排列（保证基础的最小性）。
• 修正开头为0的情况：如果排序后的第一个数字是0，说明未使用数字包含0和至少一个非0数字，此时将第一个非0数字移到最前面，后续依次拼接0和剩余数字，既保证最小又符合合法要求。

Python 实现代码 #

def find_min_unused_number(n):
    # 转换输入为已用数字的集合，O(1)查找效率
    used_digits = set(str(n))
    # 收集所有未使用的数字，转为字符串列表便于操作
    unused = [str(d) for d in range(10) if str(d) not in used_digits]
    
    # 处理极端情况（输入包含所有数字，实际不可能出现）
    if not unused:
        return ""
    
    # 若开头不是0，直接拼接即可
    if unused[0] != '0':
        return ''.join(unused)
    # 若开头是0，调整第一个非0数字到首位
    else:
        # 找到第一个非0数字的位置
        first_non_zero = next(idx for idx, digit in enumerate(unused) if digit != '0')
        # 交换首位和第一个非0数字的位置
        unused[0], unused[first_non_zero] = unused[first_non_zero], unused[0]
        return ''.join(unused)

# 测试用例
print(find_min_unused_number(6789))  # 输出: 102345
print(find_min_unused_number(12345)) # 输出: 60789
print(find_min_unused_number(0))     # 输出: 123456789
print(find_min_unused_number(10))    # 输出: 23456789

关键细节说明 #

• 使用集合存储已用数字：相比列表，集合的成员查询是O(1)时间复杂度，效率更高。
• 升序排序的必要性：确保我们从最小的数字开始构建结果，是生成最小数的基础。
• 0开头的处理逻辑：通过交换第一个非0数字到首位，既避免了非法开头，又保证了整体数字最小（因为只交换必要的位置，其余数字仍保持升序）。

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