java - "Next bigger number with the same digits"- 执行超时(16000 毫秒)- Codewars

Question

我编写了一个程序，该程序返回下一个更大的数字，该数字是用相同的数字创建的，但看起来代码的速度不够快，无法通过随机测试，并给出“执行超时(16000 毫秒)”错误。

public static String swap(String a, int i, int j)
{
    char temp;
    char[] charArray = a.toCharArray();
    temp = charArray[i] ;
    charArray[i] = charArray[j];
    charArray[j] = temp;
    return String.valueOf(charArray);
}

public static void getPermutations(String str, int l, int r, List<Long> permutations ) {
    if (l == r)
        permutations.add(Long.valueOf(str));
    else {
        for (int i = l; i <= r; i++) {
            str = swap(str, l, i);
            getPermutations(str, l + 1, r, permutations);
            str = swap(str, l, i);
        }
    }
}

public static long nextBiggerNumber(long n) {
    String numberTostring = Long.toString(n);

    List<Long> permutations = new ArrayList<>();
    getPermutations(numberTostring, 0 ,numberTostring.length() - 1, permutations);
    permutations.sort(Comparator.naturalOrder());

    for (long number : permutations) {
        if (number > n)  {
            return number;
        }
    }

    return -1;
}

你知道如何改进这段代码吗？

Answer 1

long 最多可以有 19 个十进制数字，所以有 19 个! = 121645100408832000(大约 10^17)个可能的排列。实际上很少，因为有些数字会出现不止一次；但即便如此，这对于单台计算机来说还是太大了。

我不会为您解开这个谜题，但这里有一个提示:通常下一个最大的数字看起来与原始数字非常相似。查看几个示例(如果需要，请创建更多示例):

• 312 → 321
• 26478 -> 26487
• 9378456923475 -> 9378456923547

你能找到一种方法来仅排列一次输入数字以结束下一个更大的数字吗？