Dado un número num que contiene n dígitos. El problema es encontrar el siguiente número mayor usando el mismo conjunto de dígitos en num sobre la base de la precedencia dada de dígitos. Por ejemplo, la precedencia de los dígitos se da como 1, 6, 4, 5, 2, 9, 8, 0, 7, 3, lo que simplemente significa 1 < 6 < 4 < 5 < 2 < 9 < 8 < 0 < 7 < 3 . Si no se puede formar el siguiente número mayor, imprima el número original.
Ejemplos:
Input : num = "231447"
pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3}
Output : 237144
According to the precedence of digits 1 is
being considered as the smallest digit and 3
is being considered as the largest digit.
Input : num = "471"
pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3}
Output : 471
Enfoque: Los siguientes son los pasos:
- Cree una array de prioridad [] de tamaño ’10’. Con la ayuda de la array de precedencia pre[] , asigne un número de prioridad a cada dígito en la prioridad [] donde ‘1’ se considera como la prioridad más pequeña y ’10’ como la prioridad más alta.
- Usando STL C++ next_permutation con una función de comparación definida manualmente, encuentre la siguiente permutación mayor.
C++
// C++ implementation to find the next greater number
// on the basis of precedence of digits
#include <bits/stdc++.h>
using namespace std;
#define DIGITS 10
// priority[] to store the priority of digits
// on the basis of pre[] array. Here '1' is being
// considered as the smallest priority as '10' as
// the highest priority
int priority[DIGITS];
// comparator function used for finding the
// the next greater permutation
struct compare {
bool operator()(char x, char y) {
return priority[x - '0'] < priority[y - '0'];
}
};
// function to find the next greater number
// on the basis of precedence of digits
void nextGreater(char num[], int n, int pre[]) {
memset(priority, 0, sizeof(priority));
// variable to assign priorities to digits
int assign = 1;
// assigning priorities to digits on
// the basis of pre[]
for (int i = 0; i < DIGITS; i++) {
priority[pre[i]] = assign;
assign++;
}
// find the next greater permutation of 'num'
// using the compare() function
bool a = next_permutation(num, num + n, compare());
// if the next greater permutation does not exists
// then store the original number back to 'num'
// using 'pre_permutation'.
if (a == false)
prev_permutation(num, num + n, compare());
}
// Driver program to test above
int main() {
char num[] = "231447";
int n = strlen(num);
int pre[] = {1, 6, 7, 5, 2, 9, 8, 0, 4, 3};
nextGreater(num, n, pre);
cout << "Next Greater: " << num;
return 0;
}
Producción:
Next Greater: 237144
Complejidad temporal: O(n).
Espacio Auxiliar: O(1).
Publicación traducida automáticamente
Artículo escrito por ayushjauhari14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA