Dado un número en forma de string str y un entero K , la tarea es encontrar el entero más pequeño que se puede formar después de realizar como máximo K intercambios consecutivos.
Los intercambios consecutivos significan que en un intercambio el carácter en el índice i puede intercambiarse con el carácter en el índice i – 1 o i + 1 .
Ejemplos:
Entrada: str = “76921”, K = 3
Salida: 27691
Explicación:
27691 es el número lexicográfico más pequeño posible.Entrada: str = “9438957234785635408”, K = 23
Salida: 0345989723478563548
Explicación:
0345989723478563548 es el número lexicográfico más pequeño posible.
Enfoque ingenuo: la idea más simple es generar todas las permutaciones posibles de la string dada y verificar si la string lexicográficamente más pequeña satisface las condiciones para un máximo de K intercambios. Imprime esa string.
Complejidad de tiempo: O(N!), donde N es la longitud de la string dada.
Espacio Auxiliar: O(1)
Mejor enfoque: un mejor enfoque es usar Greedy Approach . A continuación se muestran los pasos:
- Elimina el cero inicial si existe en el número dado.
- Elija el elemento más pequeño de la string str [Considere str[k] cuando K es más pequeño, de lo contrario N ].
- Coloque el elemento más pequeño en la posición 0 después de desplazar todos estos elementos 1 posición a la derecha.
- Reste el número de intercambios en los pasos anteriores de K .
- Si aún nos queda K > 0 , aplicamos el mismo procedimiento desde la siguiente posición inicial, es decir, str[2, …N], y luego lo colocamos en la primera posición.
- Así que seguimos aplicando el mismo proceso hasta que K se convierte en 0 .
Complejidad de tiempo: O(N 2 ), donde N es la longitud de la string dada.
Espacio Auxiliar: O(1)
Enfoque eficiente: la idea es utilizar el árbol de segmentos y Hashing . A continuación se muestran los pasos:
- Elimina el cero inicial si existe en el número dado.
- Almacene la posición original de los dígitos en un mapa y encuentre qué dígito se ajusta mejor a cada índice cuyo desplazamiento será menor que igual a K .
- Use un mapa para encontrar la posición original del dígito.
- Encuentre el número de dígitos que están a la derecha de la posición actual y que están desplazados, para esto, marque la posición de los cuales están desplazados en un árbol de segmento de [0 … N-1] .
- Cada Node del árbol de segmentos contiene el número de posiciones que se desplazaron. Ahora la tarea es encontrar cuántas posiciones se cambiaron en el rango [índice_actual, N-1] porque solo eso afectará la posición original.
- La nueva posición a cambiar será (original_position + number_of_right – element_shifted – i), es decir, la posición original del elemento se agrega al árbol de segmentos que se acaba de cambiar.
A continuación se muestra el programa para el enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to mark the pos as 1 that
// are shifted in string in Segtree node
void segAdd(vector<int>& seg, int start,
int end, int pos, int curr)
{
// Out of Range
if (pos < start or pos > end)
return;
// Check if we reach the position
if (start == end) {
seg[curr] = 1;
return;
}
// Initialize the mid
int mid = (start + end) / 2;
// Recursion call
segAdd(seg, start, mid, pos,
2 * curr + 1);
segAdd(seg, mid + 1, end, pos,
2 * curr + 2);
// Every node contains no of
// marked position that are
// shifted in a range
seg[curr] = seg[2 * curr + 1]
+ seg[2 * curr + 2];
return;
}
// Function to find the number of
// elements which got shifted
int segFind(
vector<int>& seg, int pos_start,
int pos_end, int start, int end,
int curr)
{
// Return 0 is the end position is
// less than start or the start
// position is greater than end
if (pos_end < start
or pos_start > end)
return 0;
if (pos_start <= start
and pos_end >= end)
return seg[curr];
// Initialize the mid
int mid = (start + end) / 2;
// Recursion call
int left = segFind(
seg, pos_start, pos_end,
start, mid, 2 * curr + 1);
int right = segFind(
seg, pos_start, pos_end,
mid + 1, end, 2 * curr + 2);
// Return the result
return left + right;
}
// Function to remove leading zeros
// from the given string str
string removeLeadingZeros(string str)
{
int i = 0;
// To store the resultant string
string ans = "";
for (; i < str[i]; i++) {
// If Initial character is 0,
// then remove it
if (str[i] == '0') {
i++;
}
// Else break
else {
break;
}
}
ans = str.substr(i - 1,
str.length());
// Return the updated string
return ans;
}
// Function to find the lexicographically
// smallest integer
string findMinimumInteger(
string arr, int k)
{
// To remove leading zeros
arr = removeLeadingZeros(arr);
int n = arr.size();
// Segment tree vector
vector<int> seg(
(2 * (int)pow(
2,
(int)(ceil(log2(n))))
- 1),
0);
// Hash to find the original
// position of the digit
unordered_map<int, list<int> > m;
for (int i = 0; i < n; i++) {
m[arr[i] - '0'].push_back(i);
}
// Resultant string variable
string res = "";
for (int i = 0; i < n; i++) {
// Place a digit from
// 0-9 which fit best
for (int digit = 0;
digit <= 9; digit++) {
if (m[digit].size() != 0) {
int original_pos
= m[digit].front();
// Find the number of
// right elements that
// are shifted from
// current element
int shift
= segFind(
seg, original_pos,
n - 1, 0, n - 1, 0);
// Mark the new position
int new_pos = original_pos
+ shift
- i;
if (new_pos <= k) {
k -= new_pos;
// Add the original position of
// the element which got shifted
segAdd(seg, 0, n - 1,
original_pos, 0);
res.push_back('0' + digit);
m[digit].pop_front();
break;
}
}
}
}
// Return the result
return res;
}
// Driver Code
int main()
{
// Given string
string s = "9438957234785635408";
// Given K swaps
int k = 23;
// Function Call
cout << findMinimumInteger(s, k)
<< endl;
}
0345989723478563548
Complejidad de tiempo: O(N * log N), donde N es la longitud de la string.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por godaraji47 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA