Dada la string numérica S de tamaño N y un entero positivo K , la tarea es encontrar el número mínimo de intercambios adyacentes requeridos en S para obtener la K -ésima string numérica más pequeña mayor que la string dada.
Ejemplos:
Entrada: S = “11112”, K = 4
Salida: 4
Explicación:
La K th (= 4 th ) string numérica más pequeña que es mayor que la string dada es “21111”. La secuencia de intercambio adyacente para llegar a la string «21111» es «11112» -> «111 21 » -> «11 21 1″ -> «1 21 11″ -> » 21 111″.
Por lo tanto, el número mínimo de intercambios adyacentes requeridos es 4.Entrada: S = “12345”, K = 1
Salida: 1
Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema:
- Almacene la copia de la string numérica actual en una variable, digamos res .
- Cree una variable, digamos totalSwaps , que almacene los intercambios mínimos requeridos.
- Dado que se requiere el K-ésimo número más grande, esta declaración es igual a encontrar la K-ésima permutación a partir de la string actual.
- Encuentre la K-ésima permutación usando la función next_permutation() .
- Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
- Si res[i] no es igual a str[i] entonces inicialice la variable start como i+1 y recorra un bucle while hasta que res[i] no sea igual a str[start] y aumente el valor de i en 1.
- Iterar un bucle hasta que i no sea igual a start e intercambiar los valores str[start] y str[start – 1] y disminuir el valor de start en 1 y aumentar el valor de totalSwaps en 1 .
- Después de realizar los pasos anteriores, imprima el valor de totalSwaps como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// of swaps required to make the Kth
// smallest string greater than str
void minSwapsKthLargest(string str, int k)
{
// Store the copy of the string
string res = str;
// Find the K-th permutation of
// the given numeric string
for (int i = 0; i < k; i++) {
next_permutation(
str.begin(), str.end());
cout<<"str = "<<str<<endl;
}
// Stores the count of swaps required
int swap_count = 0;
// Traverse the string and find the
// swaps required greedily
for (int i = 0; i < res.length(); i++) {
// If both characters do not match
if (res[i] != str[i]) {
int start = i + 1;
// Search from i+1 index
while (res[i] != str[start]) {
// Find the index to swap
start++;
}
while (i != start) {
swap(str[start], str[start - 1]);
// Swap until the characters
// are at same index
start--;
swap_count++;
}
}
}
// Print the minimum number of counts
cout << swap_count;
}
// Driver Code
int main()
{
string S = "11112";
int K = 4;
minSwapsKthLargest(S, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
static char[] next_permutation(char[] array) {
int i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
int j = array.length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
char temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}
// Function to find the minimum number
// of swaps required to make the Kth
// smallest String greater than str
static void minSwapsKthLargest(String str, int k)
{
// Store the copy of the String
char[] res = str.toCharArray();
char[] s = str.toCharArray();
// Find the K-th permutation of
// the given numeric String
for (int i = 0; i < k; i++) {
s = next_permutation(s);
}
// Stores the count of swaps required
int swap_count = 0;
// Traverse the String and find the
// swaps required greedily
for (int i = 0; i < res.length; i++) {
// If both characters do not match
if (res[i] != s[i]) {
int start = i + 1;
// Search from i+1 index
while (res[i] != s[start]) {
// Find the index to swap
start++;
}
while (i != start) {
char t = s[start];
s[start] = s[start - 1];
s[start - 1] = t;
// Swap until the characters
// are at same index
start--;
swap_count++;
}
}
}
// Print the minimum number of counts
System.out.print(swap_count);
}
// Driver Code
public static void main(String[] args) {
String S = "11112";
int K = 4;
minSwapsKthLargest(S, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python Program to implement # the above approach def next_permutation(array): i = len(array) - 1 while (i > 0 and ord(array[i - 1]) >= ord(array[i])): i -= 1 if (i <= 0): return False j = len(array) - 1 while (ord(array[j]) <= ord(array[i - 1])): j -= 1 array[j],array[i - 1] = array[i - 1],array[j] j = len(array) - 1 while (i < j): array[i],array[j] = array[j],array[i] i += 1 j -= 1 return array # Function to find the minimum number # of swaps required to make the Kth # smallest string greater than str def minSwapsKthLargest(Str, k): # Store the copy of the string res = list(Str) Str = list(Str) # Find the K-th permutation of # the given numeric string for i in range(k): next_permutation(Str) # Stores the count of swaps required swap_count = 0 # Traverse the string and find the # swaps required greedily for i in range(len(res)): # If both characters do not match if (res[i] != Str[i]): start = i + 1 # Search from i+1 index while (res[i] != Str[start]): # Find the index to swap start += 1 while (i != start): Str[start],Str[start-1] = Str[start-1],Str[start] # Swap until the characters # are at same index start -= 1 swap_count += 1 # Print the minimum number of counts print(swap_count) # Driver Code S = "11112" K = 4 minSwapsKthLargest(S, K) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
class GFG {
static char[] next_permutation(char[] array)
{
int i = array.Length - 1;
while (i > 0 && array[i - 1] >= array[i]) {
i--;
}
int j = array.Length - 1;
while (array[j] <= array[i - 1]) {
j--;
}
char temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.Length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}
// Function to find the minimum number
// of swaps required to make the Kth
// smallest string greater than str
static void minSwapsKthLargest(string str, int k)
{
// Store the copy of the string
string res = str;
char[] str1 = str.ToCharArray();
// Find the K-th permutation of
// the given numeric string
for (int i = 0; i < k; i++) {
next_permutation(str1);
}
// Stores the count of swaps required
int swap_count = 0;
// Traverse the string and find the
// swaps required greedily
for (int i = 0; i < res.Length; i++) {
// If both characters do not match
if (res[i] != str1[i]) {
int start = i + 1;
// Search from i+1 index
while (res[i] != str1[start]) {
// Find the index to swap
start++;
}
while (i != start) {
char temp = str1[start];
str1[start] = str1[start - 1];
str1[start - 1] = temp;
// Swap until the characters
// are at same index
start--;
swap_count++;
}
}
}
// Print the minimum number of counts
Console.WriteLine(swap_count);
}
// Driver Code
public static void Main()
{
string S = "11112";
int K = 4;
minSwapsKthLargest(S, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
function next_permutation(array)
{
var i = array.length - 1;
while (i > 0 && array[i - 1].charCodeAt(0) >= array[i].charCodeAt(0)) {
i--;
}
if (i <= 0) {
return false;
}
var j = array.length - 1;
while (array[j].charCodeAt(0) <= array[i - 1].charCodeAt(0)) {
j--;
}
var temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
return array;
}
// Function to find the minimum number
// of swaps required to make the Kth
// smallest string greater than str
function minSwapsKthLargest(str, k)
{
// Store the copy of the string
let res = str.split('');
str = str.split('')
// Find the K-th permutation of
// the given numeric string
for (let i = 0; i < k; i++) {
next_permutation(
str);
}
// Stores the count of swaps required
let swap_count = 0;
// Traverse the string and find the
// swaps required greedily
for (let i = 0; i < res.length; i++) {
// If both characters do not match
if (res[i] != str[i]) {
let start = i + 1;
// Search from i+1 index
while (res[i] != str[start]) {
// Find the index to swap
start++;
}
while (i != start) {
let temp = str[start];
str[start] = str[start - 1]
str[start - 1] = temp;
// Swap until the characters
// are at same index
start--;
swap_count++;
}
}
}
// Print the minimum number of counts
document.write(swap_count);
}
// Driver Code
let S = "11112";
let K = 4;
minSwapsKthLargest(S, K);
// This code is contributed by Potta Lokesh
</script>
Producción:
4
Complejidad temporal: O(N*(N + K))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA