Dada una array de enteros arr[] y una string binaria str de longitud N , la tarea es reorganizar la array dada intercambiando los elementos de la array de los índices que tienen el mismo carácter en la string, de modo que el número formado por los elementos de la array reorganizada como dígitos es el máximo posible.
Ejemplos:
Entrada: arr[]={1, 3, 4, 2}, str=”0101”
Salida: 4 3 1 2
Explicación:
Dado que arr[0] es menor que arr[2], cámbielos. Por lo tanto, el número máximo posible de la array es 4, 3, 1, 2.Entrada: arr[] = { 1, 3, 456, 6, 7, 8 }, str = “101101”
Salida: 8 7 6 456 3 1
Explicación:
Elementos de array presentes en índices de 0 caracteres: {3, 7}
Mayor número que se puede formar a partir de los dos números anteriores es 73
Elementos de array presentes en índices de 1 carácter: {1, 456, 6, 8}
El número más grande que se puede formar a partir de los dos números anteriores es 864561
Por lo tanto, el número máximo que se puede generado a partir de la array es 87645631
Enfoque : siga los pasos a continuación para resolver el problema:
- Cree dos arrays para almacenar elementos de índice de 0 caracteres y elementos de índice de 1 carácter de la array.
- Ordene las arrays para formar los números más grandes posibles a partir de estas dos arrays.
- Itere sobre str y, según los caracteres, coloque elementos de array de las arrays ordenadas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Comparison Function to sort()
int myCompare(int a, int b)
{
string X = to_string(a);
string Y = to_string(b);
// Append Y at the end of X
string XY = X.append(Y);
// Append X at the end of Y
string YX = Y.append(X);
// Compare and return greater
return XY.compare(YX) < 0 ? 1 : 0;
}
// Function to return the rearranged
// array in the form of largest
// possible number that can be formed
void findMaxArray(vector<int>& arr, string& str)
{
int N = arr.size();
vector<int> Z, O, ans(N);
for (int i = 0; i < N; i++) {
if (str[i] == '0') {
Z.push_back(arr[i]);
}
else {
O.push_back(arr[i]);
}
}
// Sort them in decreasing order
sort(Z.rbegin(), Z.rend(), myCompare);
sort(O.rbegin(), O.rend(), myCompare);
int j = 0, k = 0;
// Generate the sorted array
for (int i = 0; i < N; i++) {
if (str[i] == '0') {
ans[i] = Z[j++];
}
else {
ans[i] = O[k++];
}
}
for (int i = 0; i < N; i++) {
cout << ans[i] << " ";
}
}
// Driver Code
int main()
{
vector<int> arr = { 1, 3, 456, 6, 7, 8 };
string str = "101101";
findMaxArray(arr, str);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
import java.lang.*;
class GFG{
// Function to return the rearranged
// array in the form of largest
// possible number that can be formed
static void findMaxArray(int[] arr, String str)
{
int N = arr.length;
ArrayList<Integer> Z = new ArrayList<>(),
O = new ArrayList<>();
int[] ans = new int[N];
for(int i = 0; i < N; i++)
{
if (str.charAt(i) == '0')
{
Z.add(arr[i]);
}
else
{
O.add(arr[i]);
}
}
// Sort them in decreasing order
Collections.sort(Z, new Comparator<Integer>()
{
public int compare(Integer a, Integer b)
{
String X = Integer.toString(a);
String Y = Integer.toString(b);
// Append Y at the end of X
String XY = X + Y;
// Append X at the end of Y
String YX = Y + X;
// Compare and return greater
return XY.compareTo(YX) > 0 ? -1 : 1;
}
});
Collections.sort(O, new Comparator<Integer>()
{
public int compare(Integer a, Integer b)
{
String X = Integer.toString(a);
String Y = Integer.toString(b);
// Append Y at the end of X
String XY = X + Y;
// Append X at the end of Y
String YX = Y + X;
// Compare and return greater
return XY.compareTo(YX) > 0 ? -1 : 1;
}
});
int j = 0, k = 0;
// Generate the sorted array
for(int i = 0; i < N; i++)
{
if (str.charAt(i) == '0')
{
ans[i] = Z.get(j++);
}
else
{
ans[i] = O.get(k++);
}
}
for(int i = 0; i < N; i++)
{
System.out.print(ans[i] + " ");
}
}
// Driver code
public static void main (String[] args)
{
int[] arr = { 1, 3, 456, 6, 7, 8 };
String str = "101101";
findMaxArray(arr, str);
}
}
// This code is contributed by offbeat
Python3
# Python Program to implement # the above approach from functools import cmp_to_key # Function to return the rearranged # array in the form of largest # possible number that can be formed def findMaxArray(arr, strr): N = len(arr) Z = [] O = [] ans = [0]*N for i in range(N): if (strr[i] == '0'): Z.append(arr[i]) else: O.append(arr[i]) # Sort them in decreasing order Z.sort(key=cmp_to_key(lambda x, y: 1 if str(x)+str(y) < str(y)+str(x) else -1)) O.sort(key=cmp_to_key(lambda x, y: 1 if str(x)+str(y) < str(y)+str(x) else -1)) j = 0 k = 0 # Generate the sorted array for i in range(N): if (strr[i] == '0'): ans[i] = Z[j] j += 1 else: ans[i] = O[k] k += 1 for i in range(N): print(ans[i], end=" ") # Driver Code arr = [1, 3, 456, 6, 7, 8] strr = "101101" findMaxArray(arr, strr) # This code is contributed by rj13to.
8 7 6 456 3 1
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)