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

2021年3月27日17:34:22 发表评论 759 次浏览

本文概述

给定一个整数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#

// 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#

// 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
?>

输出如下：

543210

时间复杂度：O(N), 其中N是位数。

辅助空间：O(1), 哈希大小仅为10, 这是一个常数。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: