Python查找相同数字重排下一个更大数的时间复杂度优化

原方案缺陷分析 #

你当前的暴力实现存在两个核心性能问题：

• 逐次+1遍历数值，当符合要求的结果和输入差值极大时，会产生海量无效循环
• 每次循环都要对两个数字转字符串后排序比对，排序操作本身时间复杂度为O(k log k)（k为数字位数），叠加循环后总耗时完全不可控

优化算法：标准下一个排列算法 #

该算法时间复杂度仅为O(k)（k为数字位数），完全不需要遍历数值，也不需要重复排序，逻辑步骤如下：

• 将输入数字转为字符列表，方便逐位操作
• 从右向左遍历，找到第一个满足 digits[i] < digits[i+1] 的下标i：如果找不到，说明当前已经是同数字组成的最大值，直接返回-1
• 再次从右向左遍历，找到第一个满足 digits[j] > digits[i] 的下标j
• 交换digits[i]和digits[j]的值
• 将i下标右侧的所有字符反转，得到的就是最小的更大排列

优化后代码 #

def next_bigger(n):
    digits = list(str(n))
    length = len(digits)
    # 查找第一个左侧小于右侧的位置i
    i = length - 2
    while i >= 0 and digits[i] >= digits[i+1]:
        i -= 1
    if i < 0:
        return -1
    # 查找右侧第一个比digits[i]大的位置j
    j = length - 1
    while digits[j] <= digits[i]:
        j -= 1
    # 交换两个位置的值
    digits[i], digits[j] = digits[j], digits[i]
    # 反转i右侧的序列得到最小后缀
    digits[i+1:] = reversed(digits[i+1:])
    # 转回整数返回
    return int(''.join(digits))

测试用例验证 #

给定的所有测试用例均可正确返回结果：

• next_bigger(123) → 132
• next_bigger(2532) → 3225
• next_bigger(543890432) → 543892034
• next_bigger(143255555555555553223) → 143255555555555553232

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