Codewars题「相同数字组成的下一个更大数」执行超时如何优化？

原代码性能问题原因 #

• 原方案采用全排列枚举逻辑，时间复杂度为O(k!)，k为输入数字的位数。当数字位数达到10位时就需要生成362万+个排列，位数更高时计算量会呈指数级暴涨，必然触发超时错误。
• 额外的排序、遍历步骤进一步增加了不必要的性能开销。

优化方案：使用标准下一个排列算法 #

该算法时间复杂度仅为O(k)，无需生成所有排列，直接原地计算目标值。

算法步骤 #

1. 把输入数字转为字符数组，从右向左查找第一个满足digits[i] < digits[i+1]的下标i。如果找不到这样的i，说明当前已经是同数字组合的最大值，直接返回-1。
2. 再次从右向左查找第一个大于digits[i]的元素下标j。
3. 交换digits[i]和digits[j]。
4. 反转i下标之后的所有字符，得到的结果就是最小的、比原数大的同数字组合数。

优化后代码 #

public static long nextBiggerNumber(long n) {
    char[] digits = Long.toString(n).toCharArray();
    int len = digits.length;
    
    // 步骤1：找第一个i满足digits[i] < digits[i+1]
    int i = len - 2;
    while (i >= 0 && digits[i] >= digits[i+1]) {
        i--;
    }
    // 没有找到，已经是最大排列
    if (i < 0) {
        return -1;
    }
    
    // 步骤2：找第一个比digits[i]大的j
    int j = len - 1;
    while (digits[j] <= digits[i]) {
        j--;
    }
    
    // 步骤3：交换i和j位置的元素
    char temp = digits[i];
    digits[i] = digits[j];
    digits[j] = temp;
    
    // 步骤4：反转i后面的元素
    int left = i + 1, right = len - 1;
    while (left < right) {
        temp = digits[left];
        digits[left] = digits[right];
        digits[right] = temp;
        left++;
        right--;
    }
    
    // 转成long返回
    try {
        return Long.parseLong(new String(digits));
    } catch (NumberFormatException e) {
        return -1;
    }
}

优化效果说明 #

• 无需生成所有排列，仅通过3次线性遍历和1次局部反转即可得到结果，性能提升达到指数级，完全可以满足长位数数字的计算要求。
• 省去了全排列存储、排序的额外内存和时间开销。

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