个性化阅读
专注于IT技术分析

算法题:如何排列给定数字以形成最大数?|S1

本文概述

给定一个数字数组, 以产生最大值的方式排列它们。例如, 如果给定的数字为{54, 546, 548, 60}, 则排列6054854654给出最大值。如果给定的数字为{1、34、3、98、9、76、45、4}, 则排列998764543431给出最大值。

一种简单的解决方案我们想到的是按照降序对所有数字进行排序, 但是简单地排序是行不通的。例如, 548大于60, 但是输出60在548之前。第二个示例, 98大于9, 但是9在输出98之前。

那我们该怎么做呢?其思想是使用任何基于比较的排序算法。

在已使用的排序算法中,不使用默认比较,而是编写一个比较函数myCompare(),并使用它对数字进行排序。

给定两个数字X和ÿ, 应该怎样myCompare()决定要放哪个数字–我们比较两个数字XY(在X末尾附加Y)和YX(在Y末尾附加X)。如果XY较大, 则在输出中X应该在Y之前, 否则Y应该在输出之前。例如, 让X和Y为542和60。要比较X和Y, 我们比较54260和60542。由于60542大于54260, 我们将Y放在第一位。

以下是上述方法的实现。

为了使代码简单, 将数字视为字符串, 使用向量代替常规数组。

下面是上述方法的实现:

C ++

// Given an array of numbers, // program to arrange the numbers
// to form the largest number
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
// A comparison function which
// is used by sort() in
// printLargest()
int myCompare(string X, string Y)
{
     // first append Y at the end of X
     string XY = X.append(Y);
 
     // then append X at the end of Y
     string YX = Y.append(X);
 
     // Now see which of the two
     // formed numbers is greater
     return XY.compare(YX) > 0 ? 1 : 0;
}
 
// The main function that prints
// the arrangement with the
// largest value. The function
// accepts a vector of strings
void printLargest(vector<string> arr)
{
     
     // Sort the numbers using
     // library sort function. The
     // function uses our comparison
     // function myCompare() to
     // compare two strings. See
     // http://www.cplusplus.com/reference/
     // algorithm/sort/
     // for details
     sort(arr.begin(), arr.end(), myCompare);
 
     for ( int i = 0; i < arr.size(); i++)
         cout << arr[i];
}
 
// Driver program to test above functions
int main()
{
     vector<string> arr;
 
     // output should be 6054854654
     arr.push_back( "54" );
     arr.push_back( "546" );
     arr.push_back( "548" );
     arr.push_back( "60" );
     printLargest(arr);
 
     return 0;
}

Java

// Given an array of numbers, program to
// arrange the numbers to form the
// largest number
import java.util.*;
 
class GFG {
 
     // The main function that prints the
     // arrangement with the largest value.
     // The function accepts a vector of strings   
     static void printLargest(Vector<String> arr)
     {
     
         Collections.sort(arr, new
                          Comparator<String>(){
 
         // A comparison function which is used by
         // sort() in printLargest()
         @Override
         public int compare(String X, String Y) {
         
         // first append Y at the end of X
         String XY=X + Y;
         
         // then append X at the end of Y
         String YX=Y + X;
         
         // Now see which of the two
         // formed numbers
         // is greater
         return XY.compareTo(YX) > 0 ? - 1 : 1 ;
     }
     });
         
     Iterator it = arr.iterator();
 
     while (it.hasNext())
         System.out.print(it.next());
     
     }
     
     // driver program
     public static void main (String[] args)
     {
         
         Vector<String> arr;
         arr = new Vector<>();
         
         //output should be 6054854654
         arr.add( "54" );
         arr.add( "546" );
         arr.add( "548" );
         arr.add( "60" );
         printLargest(arr);
     }
}
// This code is contributed by Shubham Juneja

Python3

# Python3 Program to get the maximum
# possible integer from given array
# of integers...
 
 
# custom comparator to sort according
# to the ab, ba as mentioned in description
def comparator(a, b):
     ab = str (a) + str (b)
     ba = str (b) + str (a)
     return (( int (ba) > int (ab)) -
              ( int (ba) < int (ab)))
     
def myCompare(mycmp):
     
     # Convert a cmp= function into a key= function
     class K( object ):
         def __init__( self , obj, * args):
             self .obj = obj
         def __lt__( self , other):
             return mycmp( self .obj, other.obj) < 0
         def __gt__( self , other):
             return mycmp( self .obj, other.obj) > 0
         def __eq__( self , other):
             return mycmp( self .obj, other.obj) = = 0
         def __le__( self , other):
             return mycmp( self .obj, other.obj) < = 0
         def __ge__( self , other):
             return mycmp( self .obj, other.obj) > = 0
         def __ne__( self , other):
             return mycmp( self .obj, other.obj) ! = 0
     return K
# driver code
if __name__ = = "__main__" :
     a = [ 54 , 546 , 548 , 60 , ]
     sorted_array = sorted (a, key = myCompare(comparator))
     number = "".join([ str (i) for i in sorted_array])
     print (number)
 
# This code is Contributed by SaurabhTewary

C#

// C# program for above approach
using System.Collections.Generic;
using System;
 
namespace LargestNumberClass
{
     class LargestNumberClass
     {
         //Given a list of non-negative
         // integers, //arrange them such that they
         // form the largest number.
         //Note: The result may be very
         // large, so you need to
         //return a string instead
         // of an integer.
         public static void LargestNumberMethod(
                             List< int > inputList)
         {
             string output = string .Empty;
 
             List< string > newList = inputList.
                                     ConvertAll< string >
             ( delegate ( int i) { return i.ToString(); });
 
             newList.Sort(MyCompare);
 
             for ( int i = 0; i < inputList.Count; i++)
             {
                 output = output + newList[i];
             }
 
             if (output[0] == '0' && output.Length > 1)
             {
                 Console.Write( "0" );
             }
             Console.Write(output);
         }
 
         internal static int MyCompare( string X, string Y)
         {
             // first append Y at the end of X
             string XY = X + Y;
 
             // then append X at the end of Y
             string YX = Y + X;
 
             // Now see which of the two
             // formed numbers is greater
             return XY.CompareTo(YX) > 0 ? -1 : 1;
         }
     }
 
     class Program
     {
         static void Main( string [] args)
         {
             List< int > inputList = new List< int >()
                              { 54, 546, 548, 60 };
             LargestNumberClass.LargestNumberMethod(
                                          inputList);
         }
     }
// This code is contributed by Deepak Kumar Singh
}

的PHP

<?php
// Given an array of numbers, program
// to arrange the numbers to form the
// largest number
 
// A comparison function which is used
// by sort() in printLargest()
function myCompare( $X , $Y )
{
     // first append Y at the end of X
     $XY = $Y . $X ;
     
     // then append X at the end of Y
     $YX = $X . $Y ;
     
     // Now see which of the two formed
     // numbers is greater
     return strcmp ( $XY , $YX ) > 0 ? 1: 0;
}
 
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
function printLargest( $arr )
{
     // Sort the numbers using library sort
     // function. The function uses our
     // comparison function myCompare() to
     // compare two strings.
     // See http://www.cplusplus.com/reference/
     // algorithm/sort/
     // for details
     usort( $arr , "myCompare" );
 
     for ( $i = 0; $i < count ( $arr ) ; $i ++ )
         echo $arr [ $i ];
}
 
// Driver Code
$arr = array ( "54" , "546" , "548" , "60" );
printLargest( $arr );
 
// This code is contributed by
// rathbhupendra
?>

输出如下

6054854654

另一种方法:(使用itertools)使用Python的内置库, itertools库可用于执行此任务。

Python3

# Python3 implementation this is to use itertools.
# permutations as coded below:
 
from itertools import permutations
def largest(l):
     lst = []
     for i in permutations(l, len (l)):
         # provides all permutations of the list values, # store them in list to find max
         lst.append("".join( map ( str , i)))
     return max (lst)
 
print (largest([ 54 , 546 , 548 , 60 ])) #Output 6054854654
 
# This code is contributed by Raman Monga

输出如下

6054854654

另一种方法:使用内置排序方法, 下面是该方法的实现。

C ++

// C++ approach for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
void printLargest(vector<string> arr)
{
     sort(arr.begin(), arr.end());
     for ( int i = arr.size() - 1; i >= 0; i--)
         cout << arr[i];
}
 
// Driver code
int main()
{
     vector<string> arr;
 
     // Output should be 6054854654
     arr.push_back( "54" );
     arr.push_back( "546" );
     arr.push_back( "548" );
     arr.push_back( "60" );
     printLargest(arr);
}
 
// This code is contributed by gauravrajput1

Java

// Java approach for the above approach
import java.util.*;
 
class GFG
{
 
     // The main function that prints the
     // arrangement with the largest value.
     // The function accepts a vector of strings
     static void printLargest(Vector<String> arr)
     {
 
         Collections.sort(arr, Collections.
                           reverseOrder());
         Iterator it = arr.iterator();
 
         while (it.hasNext())
             System.out.print(it.next());
     }
 
     // Driver program
     public static void main(String[] args)
     {
 
         Vector<String> arr;
         arr = new Vector<>();
 
         // output should be 6054854654
         arr.add( "54" );
         arr.add( "546" );
         arr.add( "548" );
         arr.add( "60" );
         printLargest(arr);
     }
}

Python3

# Python3 approach for the
# above approach
 
# The main function that
# prints the arrangement
# with the largest value.
# The function accepts a
# vector of strings
def printLargest(arr):
   
     arr.sort(reverse = True )
     number = "".join([ str (i) for i in arr])
     print (number)
 
# Driver code
if __name__ = = '__main__' :
   
     arr = [ "54" , "546" , "548" , "60" ];
     
     # Output should be 6054854654
     printLargest(arr);
 
# This code is contributed by gauravrajput1

C#

// C# approach for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
static void printLargest(List<String> arr)
{
   arr.Sort();
   arr.Reverse();
   
   foreach (String str in arr)
     Console.Write(str);
}
 
// Driver code
public static void Main(String[] args)
{
   List<String> arr;
   arr = new List<String>();
 
   arr.Add( "54" );
   arr.Add( "546" );
   arr.Add( "548" );
   arr.Add( "60" );
   printLargest(arr);
}
}
 
// This code is contributed by Rajput-Ji

输出如下

6054854654

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

赞(0) 打赏
未经允许不得转载:srcmini » 算法题:如何排列给定数字以形成最大数?|S1
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏