如何通过重新排列给定数组中的所有元素而不将其转换为字符串来找到最大的级联数？

Question

问题：打印可通过串联给定数组的所有元素（以换行符分隔）来构造的最大数字。

约束：

• 1 <= N <= 1000
• 0 <= ar [i] <= 1000

定义：

• N是数组的大小

• ar [i]表示数组元素，其值可以在0到1000之间

到目前为止我的代码：

import java.io.*;
import java.util.*;

public class Solution 

{

    static int ans=0, orig_count=0;

    public static void main(String[] args)
    {

          Scanner scan=new Scanner(System.in);

          int T=scan.nextInt();

          while(T!=0)
         {
             solve();
             T-=1;
         }

    }

    void solve()
    {
        int N,count=0,n;


        Scanner scan=new Scanner(System.in);
        N=scan.nextInt()

        int[] ar=new int[N];
        int[] vis=new int[N];
        for(int i=0;i<N;i++)
        {
            ar[i]=scan.nextInt();
            vis[i]=0;
            n=ar[i];
            while(n!=0)
           {
                n/=10;
                count++;//It counts the number of digits of all elements in the given array
           }

       }      

       int index=0,val=0;
       int x=0;

       recur(ar,vis,index,N,count,val,a);
       System.out.println(ans);
    }

    static void recur(int ar[],int vis[],int index,int N,int count,int val,int a)
    {
        if(index==N)
        {
            ans=Math.max(ans,val);
            return;
        }
        for(int i=0,j=0;i<N;i++,j++)
        {
            if(vis[i]==0)
            {
                vis[i]=1;
                a=counter(ar[i]);//counter returns no. of digits in the current element
                count-=a;//this returned value is subtracted from the count(which is the number of digits of all elements in the array)

                val+=ar[i]*(Math.pow(10,count));// now the corresponding digit's place is multiplied with the element to make up the number

                recur(ar,vis,index+1,N,count,val,a);
                vis[i]=0;
                val-=ar[i]*(Math.pow(10,count));
                count+=a;
            }
        }
    }
    static int counter(int val)
    {
        int count=0;
        while(val!=0)
        {
            val/=10;
            count++;
        }
        return count;
    }
}

Answer 1

此代码不适用于大数，在时间复杂度方面也不是有效的解决方案

import java.io.*;
import java.util.*;


public class Solution 

{

    static long ans=0, orig_count=0;

    public static void main(String[] args)
    {
        int N,count=0;
        long n;


        Scanner scan=new Scanner(System.in);
        N=scan.nextInt();

        long[] ar=new long[N];
        long[] vis=new long[N];
        for(int i=0;i<N;i++)
        {
            ar[i]=scan.nextLong();
            vis[i]=0;
            n=ar[i];
            while(n!=0)
           {
                n/=10;
                count++;//It counts the number of digits of all elements in the given array
           }

       }      

       int index=0;
       long val=0,a=0;
       int x=0;

       recur(ar,vis,index,N,count,val,a);
       System.out.println(ans);
    }

    static void recur(long ar[],long vis[],int index,int N,int count,long val,long a)
    {
        if(index==N)
        {
            ans=Math.max(ans,val);
            return;
        }
        for(int i=0,j=0;i<N;i++,j++)
        {
            if(vis[i]==0)
            {
                vis[i]=1;
                a=counter(ar[i]);//counter returns no. of digits in the current element
                count-=a;//this returned value is subtracted from the count(which is the number of digits of all elements in the array)

                val+=ar[i]*(Math.pow(10,count));// now the corresponding digit's place is multiplied with the element to make up the number

                recur(ar,vis,index+1,N,count,val,a);
                vis[i]=0;
                val-=ar[i]*(Math.pow(10,count));
                count+=a;
            }
        }
    }
    static long counter(long val)
    {
        int count=0;
        while(val!=0)
        {
            val/=10;
            count++;
        }
        return count;
    }
}