Dado un entero positivo N , la tarea es encontrar el mayor valor posible de N después de realizar cualquier número de intercambios entre dígitos que están presentes en posiciones con la misma paridad.
Ejemplos :
Entrada : N = 12345
Salida : 54321
Explicación : Intercambie 1 con 5 [ambos en posiciones impares]
y 2 con 4 [ambos en posiciones pares] para obtener 54321.Entrada : N = 738946
Salida : 897643
Enfoque :
El problema se puede resolver almacenando dígitos impares indexados e incluso indexados en dos maxHeaps y creando un nuevo número que tenga ambos dígitos indexados de paridad ordenados en orden descendente.
Los siguientes pasos se pueden utilizar para resolver este problema:
- Inicializa 2 maxHeaps pares e impares .
- Itere sobre los dígitos del número y almacene los dígitos indexados pares en maxHeap par y los dígitos indexados impares en maxHeap impar.
- Cree un nuevo número extrayendo valores de maxHeaps, ahora el nuevo número tendría tanto dígitos indexados pares como dígitos indexados impares en orden decreciente.
- Devuelve este número ya que es el máximo.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return largest
// combination of integer
int largestInteger(int num)
{
// Declare two MaxHeap for
// even and odd index
priority_queue<int> Even;
priority_queue<int> Odd;
int C = 0, t = num;
// Calculate No of Digits in N
while (t) {
C++;
t /= 10;
}
// If last digit index is even then set
// flag = 1 else flag = 0
bool flag = C & 1 ? 1 : 0;
// Push even indexed element in Even MaxHeap
// and odd indexed element in Odd MaxHeap
while (num) {
if (flag)
Even.push(num % 10);
else
Odd.push(num % 10);
flag = !flag;
num /= 10;
}
// Initialize answer
int ans = 0;
// While both the Heap is non empty
while (!Even.empty() && !Odd.empty()) {
ans = (ans * 10 + Even.top());
Even.pop();
ans = (ans * 10 + Odd.top());
Odd.pop();
}
// If there is extra even index element uf
// Count of digit is odd
if (C & 1)
ans = ans * 10 + Even.top();
// Return answer
return ans;
}
// Driver Code
int main()
{
int N = 738946;
// Function call
cout << largestInteger(N) << endl;
return 0;
}
897643
Complejidad temporal: O(log N)
Espacio auxiliar: O(log N)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA