求大于n2的n1最小排列数：Java代码输出异常求助

问题回顾 #

给定两个整数n1和n2，需找出n1的最小排列数，要求该排列数大于n2；若无法实现则输出"Invalid"。我尝试编写了Java代码，但未得到正确输出。目前代码会打印所有大于n2的排列数，而非仅其中最小的那个。

你的原始代码如下：

import java.util.*;
class kbc{
    public static void main (String args[]) throws Exception {
        int n1=124;
        int n2=320;
        String s1 = "";
        s1+= n1;
        String s2 = "";
        s2+= n2;
        if(s2.length()>s1.length())
            System.out.println("Invalid");
        else{
            int[] ad = new int[s1.length()];
            for (int i=0; i<s1.length();i++){
                ad[i]= s1.charAt(i)-'0';
            }
            printSmallest(ad,n2,0);
        }
    }
    static void printSmallest(int[] a, int n2, int k) {
        int snum;
        int saved= Integer.MAX_VALUE;
        String s="";
        if (k == a.length) {
            for (int i = 0; i < a.length; i++) {
                s=s+a[i];
            }
            snum = Integer.parseInt(s);
            if(snum>n2){
                if(snum<saved){
                    saved=snum;
                }
                System.out.println(saved);
            }
        }
        else{
            for (int i = k; i < a.length; i++){
                int temp = a[k];
                a[k] = a[i];
                a[i] = temp;
                printSmallest(a,n2, k + 1);
                temp = a[k];
                a[k] = a[i];
                a[i] = temp;
            }
        }
    }
}

问题分析 #

你代码的核心问题出在状态共享和输出时机：

• saved变量是在递归的叶子节点（k == a.length）里每次重新初始化的，每次判断时它都是Integer.MAX_VALUE，根本没法记录全局最小的符合条件的数。
• 你每次找到符合条件的排列就直接打印，所以会输出所有大于n2的排列，而不是最后输出最小的那个。
• 另外还遗漏了一种情况：当n1和n2长度相同，但所有排列都不大于n2时，也需要输出"Invalid"，你的代码现在没处理这种场景。

修正后的代码 #

我调整了代码结构，把saved改成类成员变量来共享状态，并且在递归结束后统一输出结果：

import java.util.*;

class kbc {
    // 用类成员变量保存全局最小的符合条件的数
    private static int minValidNum = Integer.MAX_VALUE;

    public static void main(String args[]) throws Exception {
        int n1 = 124;
        int n2 = 320;
        String s1 = String.valueOf(n1);
        String s2 = String.valueOf(n2);

        // 如果n2的位数比n1多，直接输出Invalid
        if (s2.length() > s1.length()) {
            System.out.println("Invalid");
            return;
        }

        int[] digits = new int[s1.length()];
        for (int i = 0; i < s1.length(); i++) {
            digits[i] = s1.charAt(i) - '0';
        }

        // 开始递归找所有排列
        findMinValidPermutation(digits, n2, 0);

        // 递归结束后判断是否找到符合条件的数
        if (minValidNum != Integer.MAX_VALUE) {
            System.out.println(minValidNum);
        } else {
            System.out.println("Invalid");
        }
    }

    static void findMinValidPermutation(int[] digits, int n2, int start) {
        if (start == digits.length) {
            // 将数字数组转成整数
            int currentNum = 0;
            for (int digit : digits) {
                currentNum = currentNum * 10 + digit;
            }
            // 如果当前数大于n2，且比已记录的最小值更小，更新最小值
            if (currentNum > n2 && currentNum < minValidNum) {
                minValidNum = currentNum;
            }
            return;
        }

        // 递归生成所有排列，注意跳过重复的数字（避免重复计算相同排列）
        Set<Integer> used = new HashSet<>();
        for (int i = start; i < digits.length; i++) {
            // 如果当前数字已经用过，跳过，避免重复排列
            if (used.contains(digits[i])) {
                continue;
            }
            used.add(digits[i]);

            // 交换当前位和起始位
            swap(digits, start, i);
            // 递归处理下一位
            findMinValidPermutation(digits, n2, start + 1);
            // 回溯，恢复交换
            swap(digits, start, i);
        }
    }

    // 交换数组中两个位置的元素
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

关键改进点 #

1. 全局状态共享：用类成员变量minValidNum来记录整个递归过程中找到的最小符合条件的数，避免每次递归都重新初始化。
2. 统一输出时机：不在递归过程中打印，而是等所有递归结束后，根据minValidNum的值判断输出结果，确保只输出最小的那个或"Invalid"。
3. 去重优化：加入了Set<Integer> used来跳过重复的数字，避免生成重复的排列，提升效率（比如n1=112时，不会重复处理相同的排列）。
4. 更严谨的数字转换：直接通过数字运算生成整数，比转字符串再解析更高效。

测试验证 #

输入n1=124，n2=320时，代码会正确输出412，符合预期。如果输入n1=321，n2=320，会输出321；如果输入n1=210，n2=300，则输出Invalid。

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