Codewars同数字集下一个更大数求解代码超时优化咨询

Codewars题目链接

本题要求：找到由和输入值完全相同的一组数字组成、且比输入值大的最小数字，不存在符合要求的数字时返回-1。

测试样例 #

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321" 
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

上述样例取自GeeksforGeeks平台

原有超时实现代码 #

import math
from random import shuffle

def next_bigger(n):
    if len(str(n)) == 1:
        return -1
    else:
        pass
    k = math.factorial(len(str(n)))
    lst2 = []
    lst3 = []
    lst4 = []
    for num in str(n):
        lst2.append(num)
    for num in lst2:
        if lst2.count(num) == len(lst2):
            return -1
        else:
            pass
    for num in lst2:
        if lst2.count(num) > 1 and num not in lst4:
            k = k/math.factorial(lst2.count(num))
            lst4.append(num)
        else:
            pass

    while True:
        shuffle(lst2)
        if int(''.join(lst2)) not in lst3:
            lst3.append(int(''.join(lst2)))
            print(len(lst3))
            pass
        if int(''.join(lst2)) in lst3:
            if len(lst3) == k:
                break
            else:
                pass
    t = sorted(lst3)
    for num in t:
        if num > n:
            return num
        else:
            pass
    return -1

原有实现逻辑说明 #

这份代码可以通过所有基础样例，但运行会触发超时，核心逻辑如下：

• 边界校验：单数字输入（如n=3）、所有位数字完全相同的输入（如n=1111）直接返回-1
• 排列数计算：用组合数学公式，扣除重复数字带来的重复排列，算出所有不重复排列的总数量
• 枚举排列：靠随机shuffle打乱数字生成排列，去重后存入列表，直到攒够所有不重复排列
• 查找结果：把所有排列排序，遍历找到第一个比原数大的值返回，没有则返回-1

问题分析与优化方案 #

靠随机洗牌枚举全排列的思路没有优化价值，天生存在致命的效率缺陷：

1. 随机洗牌会大量重复生成已经存在的排列，数字位数越长，重复命中的概率越高，无效计算占比会指数级上升
2. 哪怕能做到不重复生成所有排列，当输入数字长度到8位时，无重复的全排列就有40320个，10位时更是达到3628800个，要把所有排列存进列表再排序，时间和内存开销都会爆炸，根本无法通过长数字用例。

要解决超时问题，必须彻底替换核心枚举逻辑，使用经典的「下一个排列」算法，时间复杂度可以降到O(k)（k是数字位数），不需要生成所有排列，直接构造出目标结果，步骤如下：

1. 把输入数字转成字符列表，从右往左遍历，找到第一个满足digits[i] < digits[i+1]的位置i，如果遍历完都没找到，说明数字是完全降序排列，不存在更大的同数字数，直接返回-1
2. 再次从右往左遍历，找到第一个满足digits[j] > digits[i]的位置j
3. 交换digits[i]和digits[j]
4. 把i位置之后的所有子数组反转成升序，拼接后就是符合要求的结果。

优化后的参考实现：

def next_bigger(n):
    digits = list(str(n))
    length = len(digits)
    # 单数字边界直接返回
    if length == 1:
        return -1
    # 从右往左找第一个升序位置i
    i = length - 2
    while i >= 0 and digits[i] >= digits[i+1]:
        i -= 1
    if i == -1:
        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:])
    res = int(''.join(digits))
    return res if res > n else -1

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