java - 编程寻找数字 n1 的最小排列，但应大于另一个给定数字 n2；如果不可能，则打印 "Invalid"

Question

该问题涉及两个输入整数。我们需要找到 n1 的排列，使其成为 n2 的最小大整数。

我尝试过编码，但没有得到正确的输出。我不知道如何只打印大于 n2 的最小排列。我的代码正在打印大于 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;
        }
        }  
    }
}

预期输出:

412

代码输出:

421
412

Answer 1

您选择字符进行排列的方式导致了问题。如果您按照 ASCII 值的升序选择字符，那么这不会有问题。得到你想要的号码后，你可以告诉递归“好吧，我已经找到了答案，不要再打电话了”。你可以检查这个代码。我对你的代码改动不大。

class kbc {

    private static boolean taken[];
    private static boolean found = false;
    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 {
            taken = new boolean[s1.length()];
            char[] ad = new char[s1.length()];
            char[] tempArray = s1.toCharArray();
            Arrays.sort(tempArray);
            s1 = new String(tempArray);
            printSmallest(ad, s1, n2,0);
        }
    }
    static void printSmallest(char[] a, String s1, int n2, int k) 
    {
        if(found)
            return;
        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;
                    found = true;
                }
                System.out.println(saved);
            }

        }
        else{ 
            for (int i = 0; i < a.length; i++){
                if(!taken[i] && !found) {
                    taken[i] = true;
                    a[k] = s1.charAt(i);
                    printSmallest(a, s1, n2, k + 1);
                    taken[i] = false;
                }
            }
        }  
    }
}