算法：如何排列给定数字以形成最大数？|S2

本文概述

• Java
• python

给定一个非负数(整数范围)的数组, 需要按某种顺序排列它们, 以便给出最大数。例如, 给定的数组是A [1、34、3、98、9、76、45、4、12、121]。如果我们按以下顺序排列这些数字A [9、98、76、45、4、34、3、12、121、1], 则通过将它们结合起来, 我们将得到” 99876454343121211″作为最大数字。

例子：

Input :  [1, 34, 3, 98, 9, 76, 45, 4, 12, 121]
Output : 99876454343121211

Input :  [12, 121]
Output : 12121

In设置1, 我们已经讨论了执行此操作的方法。在这一组中, 我们将讨论另一种逻辑。

1)找出最大位数的位数。令数字为n。

2)创建所有数字的扩展版本。在扩展版本中, 我们将n的数字与其自身连接起来并截断多余的数字, 从而形成n + 1个数字。

3)根据原始数字的扩展值对它们进行排序。

4)连接排序的数字将产生所需的结果。

Java

// Java program to arrange the numbers to form the
// largest number
import java.math.BigInteger;
import java.util.*;
  
public class LargestNumber
{
     // method that returns largest number form
     public static String largestNumber(List<Integer> arr)
     {
         // finding number of digits in maximum element
         // present in array
         int n =
          Collections.max(arr).toString().length();
  
         ArrayList<ExtendedNum> en =
                        new ArrayList<ExtendedNum>();
         for ( int i = 0 ; i < arr.size(); i++)
             en.add( new ExtendedNum(arr.get(i), n));
  
         // sort based on modified value
         Collections.sort(en, (p1, p2) ->
          ( int )(p2.modifiedValue - p1.modifiedValue));
  
         StringBuilder sb = new StringBuilder();
         for ( int i = 0 ; i < en.size(); i++)
             sb.append( new StringBuilder
             (Long.toString(en.get(i).originalValue)));
  
  
         // To remove any zeroes at head.
         BigInteger bi = new BigInteger(sb.toString());
  
         return bi.toString();
     }
  
     // Driver method
     public static void main(String[] args)
     {
         Integer arr[] = { 1 , 34 , 3 , 98 , 9 , 76 , 45 , 4 , 12 , 121 };
         List<Integer> l = Arrays.asList(arr);
  
         System.out.println(largestNumber(l));
     }
}
  
// A utility class to generate new value
class ExtendedNum
{
     int originalValue;
     long modifiedValue;
  
     public ExtendedNum( int originalValue, int n)
     {
         this .originalValue = originalValue;
         String s = Integer.toString(originalValue);
         StringBuilder sb = new StringBuilder(s);
         StringBuilder ans = new StringBuilder();
         while (ans.length() <= n + 1 )
             ans.append(sb);
  
         s = ans.toString().substring( 0 , n + 1 );
         modifiedValue = Long.parseLong(s);
     }
  
     public String toString()
     {
         return "[" + modifiedValue +
                 ", " + originalValue + "]" ;
     }
}

python

# Python program to find largest
# number from the given values
# function that return largest
# possible number
def largestNumber(array):
      
     # extval is a empty list for extended 
     # values and ans for calculating answer
     extval, ans = [], ""
      
     # calculating the length of largest number
     # from given and add 1 for further operation
     l = len ( str ( max (array))) + 1
      
     # iterate given values and 
     # calculating extended values
     for i in array:
         temp = str (i) * l
          
         # make tuple of extended value and 
         # equivalant original value then 
         # append to list
         extval.append((temp[:l:], i))
      
     # sort extval in descending order
     extval.sort(reverse = True )
      
     # iterate extended values
     for i in extval:
          
         # concatinate original value equivalant
         # to extended value into ans variable
         ans + = str (i[ 1 ])
  
     if int (ans) = = 0 :
         return "0"
     return ans
  
# Driver code
a = [ 1 , 34 , 3 , 98 , 9 , 76 , 45 , 4 , 12 , 121 ]
  
print (largestNumber(a))
  
# This code is contributed by Chhekur

输出如下：

99876454343121211

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。