Dada una array de n números. Dispóngalos de manera que produzca el mayor valor. Al disponer el orden de los números pares entre sí y el orden de los números impares entre sí, se debe mantener respectivamente.
Ejemplos:
Input : {78, 81, 88, 79, 117, 56}
Output : 8179788856117
The numbers are arranged in the order:
81 79 78 88 56 117 and then
concatenated.
The odd numbers 81 79 117 and
The even numbers 78 88 56 maintain
their orders as in the original array.
Input : {400, 99, 76, 331, 65, 18}
Output : 99400763316518
Este problema es una variación del problema Ordena los números dados para formar el número más grande . En este problema, encontramos el número más grande con ciertas restricciones, que es que el orden de los números pares e impares debe mantenerse en el resultado final y, por lo tanto, pretende tener una solución de complejidad de tiempo O(n).
Los siguientes son pasos para encontrar el número más grande manteniendo el orden de los números pares e impares.
- Divida los números de la array original en 2 arrays even[] y odd[] . Mientras se divide, se debe mantener el orden de los números.
- Combine arrays pares e impares y, mientras se fusiona, siga la condición. Sea X un elemento de un arreglo y Y un elemento de otro arreglo. Compare XY (Y añadido a X) e YX (X añadido a Y). Si XY es más grande, agregue X al resultado final; de lo contrario, agregue Y al resultado final.
C++
// C++ implementation to form the biggest number
// by arranging numbers in certain order
#include <bits/stdc++.h>
using namespace std;
// function to merge the even and odd list
// to form the biggest number
string merge(vector<string> arr1, vector<string> arr2)
{
int n1 = arr1.size();
int n2 = arr2.size();
int i = 0, j = 0;
// to store the final biggest number
string big = "";
while (i < n1 && j < n2)
{
// if true then add arr1[i] to big
if ((arr1[i]+arr2[j]).compare((arr2[j]+arr1[i])) > 0)
big += arr1[i++];
// else add arr2[j] to big
else
big += arr2[j++];
}
// add remaining elements
// of arr1 to big
while (i < n1)
big += arr1[i++];
// add remaining elements
// of arr2 to big
while (j < n2)
big += arr2[j++] ;
return big;
}
// function to find the biggest number
string printLargest(vector<string> arr, int n)
{
vector<string> even, odd;
for (int i=0; i<n; i++)
{
int lastDigit = arr[i].at(arr[i].size() - 1) - '0';
// inserting even numbers
if (lastDigit % 2 == 0)
even.push_back(arr[i]);
// inserting odd numbers
else
odd.push_back(arr[i]);
}
// merging both the array
string biggest = merge(even, odd);
// final required biggest number
return biggest;
}
// Driver program to test above
int main()
{
// arr[] = {78, 81, 88, 79, 117, 56}
vector<string> arr;
arr.push_back("78");
arr.push_back("81");
arr.push_back("88");
arr.push_back("79");
arr.push_back("117");
arr.push_back("56");
int n = arr.size();
cout << "Biggest number = "
<< printLargest(arr, n);
return 0;
}
Java
import java.util.Vector;
// Java implementation to form the biggest number
// by arranging numbers in certain order
class GFG
{
// function to merge the even and odd list
// to form the biggest number
static String merge(Vector<String> arr1,
Vector<String> arr2)
{
int n1 = arr1.size();
int n2 = arr2.size();
int i = 0, j = 0;
// to store the final biggest number
String big = "";
while (i < n1 && j < n2)
{
// if true then add arr1[i] to big
if ((arr1.get(i) + arr2.get(j)).
compareTo((arr2.get(j) + arr1.get(i))) > 0)
{
big += arr1.get(i++);
}
// else add arr2[j] to big
else
{
big += arr2.get(j++);
}
}
// add remaining elements
// of arr1 to big
while (i < n1)
{
big += arr1.get(i++);
}
// add remaining elements
// of arr2 to big
while (j < n2)
{
big += arr2.get(j++);
}
return big;
}
// function to find the biggest number
static String printLargest(Vector<String> arr, int n)
{
Vector<String> even = new Vector<String>(),
odd = new Vector<String>();
for (int i = 0; i < n; i++)
{
int lastDigit = arr.get(i).
charAt(arr.get(i).length() - 1) - '0';
// inserting even numbers
if (lastDigit % 2 == 0)
{
even.add(arr.get(i));
}
// inserting odd numbers
else
{
odd.add(arr.get(i));
}
}
// merging both the array
String biggest = merge(even, odd);
// final required biggest number
return biggest;
}
// Driver code
public static void main(String[] args)
{
Vector<String> arr = new Vector<String>();
arr.add("78");
arr.add("81");
arr.add("88");
arr.add("79");
arr.add("117");
arr.add("56");
int n = arr.size();
System.out.println("Biggest number = " +
printLargest(arr, n));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation to form the biggest number
# by arranging numbers in certain order
# function to merge the even and odd list
# to form the biggest number
def merge(arr1, arr2):
n1 = len(arr1)
n2 = len(arr2)
i, j = 0, 0
# to store the final biggest number
big = ""
while (i < n1 and j < n2):
# if true then add arr1[i] to big
if (int(arr1[i]+arr2[j]) - (int(arr2[j]+arr1[i])) > 0):
big += arr1[i]
i += 1
# else add arr2[j] to big
else:
big += arr2[j]
j += 1
# add remaining elements
# of arr1 to big
while (i < n1):
big += arr1[i]
i += 1
# add remaining elements
# of arr2 to big
while (j < n2):
big += arr2[j]
j += 1
return big
# function to find the biggest number
def printLargest(arr, n):
even = []
odd = []
for i in range(n):
lastDigit = int(arr[i][-1])
# inserting even numbers
if (lastDigit % 2 == 0):
even.append(arr[i])
# inserting odd numbers
else:
odd.append(arr[i])
# merging both the array
biggest = merge(even, odd)
# final required biggest number
return biggest
# Driver program to test above
arr = ['78', '81', '88', '79', '117', '56']
n = len(arr)
print("Biggest number =", printLargest(arr, n))
# This code is contributed by phasing17
C#
// C# implementation to form the biggest number
// by arranging numbers in certain order
using System;
using System.Collections.Generic;
class GFG
{
// function to merge the even and odd list
// to form the biggest number
static String merge(List<String> arr1,
List<String> arr2)
{
int n1 = arr1.Count;
int n2 = arr2.Count;
int i = 0, j = 0;
// to store the final biggest number
String big = "";
while (i < n1 && j < n2)
{
// if true then Add arr1[i] to big
if ((arr1[i] + arr2[j]).CompareTo((arr2[j] +
arr1[i])) > 0)
{
big += arr1[i++];
}
// else Add arr2[j] to big
else
{
big += arr2[j++];
}
}
// Add remaining elements
// of arr1 to big
while (i < n1)
{
big += arr1[i++];
}
// Add remaining elements
// of arr2 to big
while (j < n2)
{
big += arr2[j++];
}
return big;
}
// function to find the biggest number
static String printLargest(List<String> arr, int n)
{
List<String> even = new List<String>(),
odd = new List<String>();
for (int i = 0; i < n; i++)
{
int lastDigit = arr[i][arr[i].Length - 1] - '0';
// inserting even numbers
if (lastDigit % 2 == 0)
{
even.Add(arr[i]);
}
// inserting odd numbers
else
{
odd.Add(arr[i]);
}
}
// merging both the array
String biggest = merge(even, odd);
// final required biggest number
return biggest;
}
// Driver code
public static void Main()
{
List<String> arr = new List<String>();
arr.Add("78");
arr.Add("81");
arr.Add("88");
arr.Add("79");
arr.Add("117");
arr.Add("56");
int n = arr.Count;
Console.WriteLine("Biggest number = " +
printLargest(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation to form the biggest number
// by arranging numbers in certain order
// function to merge the even and odd list
// to form the biggest number
function merge(arr1, arr2)
{
let n1 = arr1.length;
let n2 = arr2.length;
let i = 0, j = 0;
// to store the final biggest number
let big = "";
while (i < n1 && j < n2)
{
// if true then add arr1[i] to big
if ((arr1[i]+arr2[j]).localeCompare((arr2[j]+arr1[i])) > 0)
big += arr1[i++];
// else add arr2[j] to big
else
big += arr2[j++];
}
// add remaining elements
// of arr1 to big
while (i < n1)
big += arr1[i++];
// add remaining elements
// of arr2 to big
while (j < n2)
big += arr2[j++] ;
return big;
}
// function to find the biggest number
function printLargest(arr, n)
{
let even = [];
let odd = [];
for (let i=0; i<n; i++)
{
let lastDigit = arr[i].charCodeAt(arr[i].length - 1) - '0';
// inserting even numbers
if (lastDigit % 2 == 0)
even.push(arr[i]);
// inserting odd numbers
else
odd.push(arr[i]);
}
// merging both the array
let biggest = merge(even, odd);
// final required biggest number
return biggest;
}
// Driver program to test above
// arr[] = {78, 81, 88, 79, 117, 56}
let arr = [];
arr.push("78");
arr.push("81");
arr.push("88");
arr.push("79");
arr.push("117");
arr.push("56");
let n = arr.length;
document.write("Biggest number = "
+ printLargest(arr, n));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
8179788856117
Complejidad de tiempo: O(n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA