算法（如何查找可以用给定数字形成的最大数字（））

本文概述

C ++
Java
Python3
C#
的PHP
C ++
Java
Python 3
C#
的PHP

给定一个整数arr []数组, 表示一个数字。任务是编写一个程序, 以使用这些数字生成最大数量的数字。
注意：数组中的数字在0到9之间。即0 < arr [i] < 9。
例子:

Input : arr[] = {4, 7, 9, 2, 3} Output : Largest number: 97432 Input : arr[] = {8, 6, 0, 4, 6, 4, 2, 7} Output : Largest number: 87664420

天真的方法：天真的方法是对给定的数字数组进行排序降序排列然后使用数组中的数字形成数字, 并保持数字顺序与排序数组中的数字顺序相同。
时间复杂度：O(N logN), 其中N是位数。
下面是上述想法的实现：
C ++

// C++ program to generate largest possible // number with given digits #include < bits/stdc++.h> using namespace std; // Function to generate largest possible // number with given digits int findMaxNum( int arr[], int n) { // sort the given array in // descending order sort(arr, arr+n, greater< int > ()); int num = arr[0]; // generate the number for ( int i=1; i< n; i++) { num = num*10 + arr[i]; }return num; }// Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 0}; int n = sizeof (arr)/ sizeof (arr[0]); cout< < findMaxNum(arr, n); return 0; }

Java

// Java program to generate largest // possible number with given digits import java.*; import java.util.Arrays; class GFG { // Function to generate largest // possible number with given digits static int findMaxNum( int arr[], int n) { // sort the given array in // ascending order and then // traverse into descending Arrays.sort(arr); int num = arr[ 0 ]; // generate the number for ( int i = n - 1 ; i > = 0 ; i--) { num = num * 10 + arr[i]; }return num; }// Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 0 }; int n = arr.length; System.out.println(findMaxNum(arr, n)); } }// This code is contributed by mits

Python3

# Python3 program to generate largest possible # number with given digits# Function to generate largest possible # number with given digits def findMaxNum(arr, n) :# sort the given array in # descending order arr.sort(reverse = True )# initialize num with starting # element of an arr num = arr[ 0 ]# generate the number for i in range ( 1 , n) : num = num * 10 + arr[i]return num# Driver code if __name__ = = "__main__" :arr = [ 1 , 2 , 3 , 4 , 5 , 0 ]n = len (arr)print (findMaxNum(arr, n))

// C#program to generate largest // possible number with given digits using System; public class GFG{ // Function to generate largest // possible number with given digits static int findMaxNum( int []arr, int n) { // sort the given array in // ascending order and then // traverse into descending Array.Sort(arr); int num = arr[0]; // generate the number for ( int i = n - 1; i > = 0; i--) { num = num * 10 + arr[i]; }return num; }// Driver code static public void Main (){ int []arr = {1, 2, 3, 4, 5, 0}; int n = arr.Length; Console.WriteLine(findMaxNum(arr, n)); } }// This code is contributed by Sachin..

的PHP

< ?php // PHP program to generate // largest possible number // with given digits// Function to generate // largest possible number // with given digits function findMaxNum(& $arr , $n ) { // sort the given array // in descending order rsort( $arr ); $num = $arr [0]; // generate the number for ( $i = 1; $i < $n ; $i ++) { $num = $num * 10 + $arr [ $i ]; } return $num ; }// Driver code $arr = array (1, 2, 3, 4, 5, 0); $n = sizeof( $arr ); echo findMaxNum( $arr , $n ); // This code is contributed // by ChitraNayal ?>

输出如下：

543210

高效方法：一种有效的方法是观察我们必须仅使用0-9之间的数字来形成数字。因此, 我们可以创建大小为10的哈希来存储给定数组中数字出现的次数进入哈希表。哈希表中的键将是0到9之间的数字, 其值将是它们在数组中出现的次数。
最后, 从数字9开始按降序打印数字。
下面是上述方法的实现：
C ++

// C++ program to generate largest possible // number with given digits #include < bits/stdc++.h> using namespace std; // Function to generate largest possible // number with given digits void findMaxNum( int arr[], int n) { // Declare a hash array of size 10 // and initialize all the elements to zero int hash[10] = {0}; // store the number of occurrences of the digits // in the given array into the hash table for ( int i=0; i< n; i++) { hash[arr[i]]++; }// Traverse the hash in descending order // to print the required number for ( int i=9; i> =0; i--) { // Print the number of times a digits occurs for ( int j=0; j< hash[i]; j++) cout< < i; } }// Driver code int main() { int arr[] = {1, 2, 3, 4, 5, 0}; int n = sizeof (arr)/ sizeof (arr[0]); findMaxNum(arr, n); return 0; }

Java

// Java program to generate // largest possible number // with given digits class GFG {// Function to generate // largest possible number // with given digits static void findMaxNum( int arr[], int n) { // Declare a hash array of // size 10 and initialize // all the elements to zero int []hash = new int [ 10 ]; // store the number of occurrences // of the digits in the given array // into the hash table for ( int i = 0 ; i < n; i++) { hash[arr[i]]++; }// Traverse the hash in descending // order to print the required number for ( int i = 9 ; i > = 0 ; i--) { // Print the number of // times a digits occurs for ( int j = 0 ; j < hash[i]; j++) System.out.print(i); } }// Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 0 }; int n = arr.length; findMaxNum(arr, n); } }// This code is contributed // by ChitraNayal

Python 3

# Python 3 program to generate # largest possible number # with given digits# Function to generate # largest possible number # with given digits def findMaxNum(arr, n):# Declare a hash array of # size 10 and initialize # all the elements to zero hash = [ 0 ] * 10# store the number of occurrences # of the digits in the given array # into the hash table for i in range (n): hash [arr[i]] + = 1# Traverse the hash in # descending order to # print the required number for i in range ( 9 , - 1 , - 1 ):# Print the number of # times a digits occurs for j in range ( hash [i]): print (i, end = "")# Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 0 ] n = len (arr) findMaxNum(arr, n)# This code is contributed # by ChitraNayal

// C# program to generate // largest possible number // with given digits using System; class GFG {// Function to generate // largest possible number // with given digits static void findMaxNum( int [] arr, int n) { // Declare a hash array of // size 10 and initialize // all the elements to zero int [] hash = new int [10]; // store the number of // occurrences of the // digits in the given // array into the hash table for ( int i = 0; i < n; i++) { hash[arr[i]]++; }// Traverse the hash in // descending order to // print the required number for ( int i = 9; i > = 0; i--) { // Print the number of // times a digits occurs for ( int j = 0; j < hash[i]; j++) Console.Write(i); } }// Driver code public static void Main() { int [] arr = {1, 2, 3, 4, 5, 0}; int n = arr.Length; findMaxNum(arr, n); } }// This code is contributed // by ChitraNayal

的PHP

< ?php // PHP program to generate // largest possible number // with given digits// Function to generate // largest possible number // with given digits function findMaxNum( $arr , $n ) { // Declare a hash array of // size 10 and initialize // all the elements to zero $hash = array_fill (0, 10, 0); // store the number of occurrences // of the digits in the given array // into the hash table for ( $i = 0; $i < $n ; $i ++) $hash [ $arr [ $i ]] += 1; // Traverse the hash in // descending order to // print the required number for ( $i = 9; $i > = 0; $i --)// Print the number of // times a digits occurs for ( $j = 0; $j < $hash [ $i ]; $j ++) echo $i ; }// Driver code $arr = array (1, 2, 3, 4, 5, 0); $n = sizeof( $arr ); findMaxNum( $arr , $n ); // This code is contributed // by mits ?>

输出如下：