Dado un número no negativo num . El problema es aplicar como máximo una operación de intercambio sobre el número num para que la resultante sea el número más pequeño posible. El número podría ser muy grande, por lo que se puede usar un tipo de string para almacenar el número. La entrada no contiene ceros iniciales y la salida tampoco debe contener ceros iniciales.
Nota: Debe haber el mismo conjunto de dígitos en el número resultante que en el número original.
Ejemplos:
Input : n = 9625635 Output : 2695635 Swapped the digits 9 and 2. Input : n = 1205763 Output : 1025763
Acercarse:
- Cree una array rightMin[] .
- rightMin[i] contiene el índice del dígito más pequeño que está en el lado derecho de num[i] y también más pequeño que num[i] .
- Si no existe tal dígito, entonces rightMin[i] = -1. Ahora, verifique si num[0] tiene un dígito más pequeño a la derecha que no es igual a 0.
- Si es así, intercambie el primer dígito con su dígito derecho más pequeño. De lo contrario, recorra la array rightMin[] de i = 1 a n-1 (donde n es el número total de dígitos en num ), y busque el primer elemento que tenga rightMin[i] != -1.
- Realice la operación swap(num[i], num[rightMin[i]]) y rompa.
Implementación:
C++
// C++ implementation to form the smallest
// number using at most one swap operation
#include <bits/stdc++.h>
using namespace std;
// function to form the smallest number
// using at most one swap operation
string smallestNumber(string num)
{
int n = num.size();
int rightMin[n], right;
// for the rightmost digit, there
// will be no smaller right digit
rightMin[n - 1] = -1;
// index of the smallest right digit
// till the current index from the
// right direction
right = n - 1;
// traverse the array from second
// right element up to the left
// element
for (int i = n - 2; i >= 1; i--) {
// if 'num[i]' is greater than
// the smallest digit encountered
// so far
if (num[i] >= num[right])
rightMin[i] = right;
else {
// for cases like 120000654 or 1000000321
// rightMin will be same for all 0's
// except the first from last
if (num[i] == num[i + 1]) {
rightMin[i] = right;
}
else {
rightMin[i] = -1;
right = i;
}
}
}
// special condition for the 1st digit so that
// it is not swapped with digit '0'
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] <= num[small])
small = i;
}
if (small != -1)
swap(num[0], num[small]);
else {
// traverse the 'rightMin[]' array from
// 2nd digit up to the last digit
for (int i = 1; i < n; i++) {
// if for the current digit, smaller
// right digit exists, then swap it
// with its smaller right digit and
// break
if (rightMin[i] != -1 && num[i] != num[rightMin[i]]) {
// performing the required
// swap operation
swap(num[i], num[rightMin[i]]);
break;
}
}
}
// required smallest number
return num;
}
// Driver program to test above
int main()
{
string num = "9625635";
cout << "Smallest number: "
<< smallestNumber(num);
return 0;
}
Java
// Java implementation to form the smallest
// number using at most one swap operation
import java.util.*;
import java.lang.*;
public class GeeksforGeeks {
// function to form the smallest number
// using at most one swap operation
public static String smallestNumber(String str)
{
char[] num = str.toCharArray();
int n = str.length();
int[] rightMin = new int[n];
// for the rightmost digit, there
// will be no smaller right digit
rightMin[n - 1] = -1;
// index of the smallest right digit
// till the current index from the
// right direction
int right = n - 1;
// traverse the array from second
// right element up to the left
// element
for (int i = n - 2; i >= 1; i--) {
// if 'num[i]' is greater than
// the smallest digit
// encountered so far
if (num[i] > num[right])
rightMin[i] = right;
else {
// there is no smaller right
// digit for 'num[i]'
rightMin[i] = -1;
// update 'right' index
right = i;
}
}
// special condition for the 1st
// digit so that it is not swapped
// with digit '0'
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] < num[small])
small = i;
}
if (small != -1) {
char temp;
temp = num[0];
num[0] = num[small];
num[small] = temp;
}
else {
// traverse the 'rightMin[]'
// array from 2nd digit up
// to the last digit
for (int i = 1; i < n; i++) {
// if for the current digit,
// smaller right digit exists,
// then swap it with its smaller
// right digit and break
if (rightMin[i] != -1) {
// performing the required
// swap operation
char temp;
temp = num[i];
num[i] = num[rightMin[i]];
num[rightMin[i]] = temp;
break;
}
}
}
// required smallest number
return (new String(num));
}
// driver function
public static void main(String argc[])
{
String num = "9625635";
System.out.println("Smallest number: " + smallestNumber(num));
}
}
/*This code is contributed by Sagar Shukla.*/
Python 3
# Python implementation to form the smallest
# number using at most one swap operation
# function to form the smallest number
# using at most one swap operation
def smallestNumber(num):
num = list(num)
n = len(num)
rightMin = [0]*n
right = 0
# for the rightmost digit, there
# will be no smaller right digit
rightMin[n-1] = -1;
# index of the smallest right digit
# till the current index from the
# right direction
right = n-1;
# traverse the array from second
# right element up to the left
# element
for i in range(n-2, 0, -1):
# if 'num[i]' is greater than
# the smallest digit encountered
# so far
if num[i] > num[right]:
rightMin[i] = right
else:
# there is no smaller right
# digit for 'num[i]'
rightMin[i] = -1
# update 'right' index
right = i
# special condition for the 1st digit so that
# it is not swapped with digit '0'
small = -1
for i in range(1, n):
if num[i] != '0':
if small == -1:
if num[i] < num[0]:
small = i
elif num[i] < num[small]:
small = i
if small != -1:
num[0], num[small] = num[small], num[0]
else:
# traverse the 'rightMin[]' array from
# 2nd digit up to the last digit
for i in range(1, n):
# if for the current digit, smaller
# right digit exists, then swap it
# with its smaller right digit and
# break
if rightMin[i] != -1:
# performing the required
# swap operation
num[i], num[rightMin[i]] = num[rightMin[i]], num[i]
break
# required smallest number
return ''.join(num)
# Driver Code
if __name__ == "__main__":
num = "9625635"
print("Smallest number: ", smallestNumber(num))
# This code is contributed by
# sanjeev2552
C#
// C# implementation to form the smallest
// number using at most one swap operation.
using System;
public class GeeksforGeeks {
// function to form the smallest number
// using at most one swap operation
public static String smallestNumber(String str)
{
char[] num = str.ToCharArray();
int n = str.Length;
int[] rightMin = new int[n];
// for the rightmost digit, there
// will be no smaller right digit
rightMin[n - 1] = -1;
// index of the smallest right digit
// till the current index from the
// right direction
int right = n - 1;
// traverse the array from second
// right element up to the left
// element
for (int i = n - 2; i >= 1; i--) {
// if 'num[i]' is greater than
// the smallest digit
// encountered so far
if (num[i] > num[right])
rightMin[i] = right;
else {
// there is no smaller right
// digit for 'num[i]'
rightMin[i] = -1;
// update 'right' index
right = i;
}
}
// special condition for the 1st
// digit so that it is not swapped
// with digit '0'
int small = -1;
for (int i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i] < num[0])
small = i;
}
else if (num[i] < num[small])
small = i;
}
if (small != -1) {
char temp;
temp = num[0];
num[0] = num[small];
num[small] = temp;
}
else {
// traverse the 'rightMin[]'
// array from 2nd digit up
// to the last digit
for (int i = 1; i < n; i++) {
// if for the current digit,
// smaller right digit exists,
// then swap it with its smaller
// right digit and break
if (rightMin[i] != -1) {
// performing the required
// swap operation
char temp;
temp = num[i];
num[i] = num[rightMin[i]];
num[rightMin[i]] = temp;
break;
}
}
}
// required smallest number
return (new String(num));
}
// Driver code
public static void Main()
{
String num = "9625635";
Console.Write("Smallest number: " + smallestNumber(num));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP implementation to
// form the smallest number
// using at most one swap
// operation
// function to form the
// smallest number using
// at most one swap operation
function smallestNumber($num)
{
$n = strlen($num);
$rightMin = array_fill(0, $n, -1);
$right;
// for the rightmost digit,
// there will be no smaller
// right digit
$rightMin[$n - 1] = -1;
// index of the smallest
// right digit till the
// current index from the
// right direction
$right = $n - 1;
// traverse the array from
// second right element up
// to the left element
for ($i = $n - 2; $i >= 1; $i--)
{
// if 'num[i]' is greater
// than the smallest digit
// encountered so far
if ($num[$i] > $num[$right])
$rightMin[$i] = $right;
else
{
// there is no smaller
// right digit for 'num[i]'
$rightMin[$i] = -1;
// update 'right' index
$right = $i;
}
}
// special condition for
// the 1st digit so that
// it is not swapped with
// digit '0'
$small = -1;
for ($i = 1; $i < $n; $i++)
if ($num[$i] != '0')
{
if ($small == -1)
{
if ($num[$i] < $num[0])
$small = $i;
}
else if ($num[$i] < $num[$small])
$small = $i;
}
if ($small != -1)
{
$tmp = $num[0];
$num[0] = $num[$small];
$num[$small] = $tmp;
}
else
{
// traverse the 'rightMin[]'
// array from 2nd digit up
// to the last digit
for ($i = 1; $i < $n; $i++)
{
// if for the current
// digit, smaller right
// digit exists, then
// swap it with its
// smaller right digit
// and break
if ($rightMin[$i] != -1)
{
// performing the required
// swap operation
$tmp = $num[$i];
$num[$i] = $num[$rightMin[$i]];
$num[$rightMin[$i]] = $tmp;
break;
}
}
}
// required smallest number
return $num;
}
// Driver Code
$num = "9625635";
echo "Smallest number: " .
smallestNumber($num);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation to form the smallest
// number using at most one swap operation
// function to form the smallest number
// using at most one swap operation
function smallestNumber(num)
{
var n = num.length;
var rightMin = Array(n).fill(0), right;
// for the rightmost digit, there
// will be no smaller right digit
rightMin[n - 1] = -1;
// index of the smallest right digit
// till the current index from the
// right direction
right = n - 1;
// traverse the array from second
// right element up to the left
// element
for (var i = n - 2; i >= 1; i--) {
// if 'num[i]' is greater than
// the smallest digit encountered
// so far
if (num[i].charCodeAt(0) >= num[right].charCodeAt(0))
rightMin[i] = right;
else {
// for cases like 120000654 or 1000000321
// rightMin will be same for all 0's
// except the first from last
if (num[i] == num[i + 1]) {
rightMin[i] = right;
}
else {
rightMin[i] = -1;
right = i;
}
}
}
// special condition for the 1st digit so that
// it is not swapped with digit '0'
var small = -1;
for (var i = 1; i < n; i++)
if (num[i] != '0') {
if (small == -1) {
if (num[i].charCodeAt(0) < num[0].charCodeAt(0))
small = i;
}
else if (num[i].charCodeAt(0) <= num[small].charCodeAt(0))
small = i;
}
if (small != -1)
{
var tmp = num[0]
num[0] = num[small]
num[small] = tmp
}
else {
// traverse the 'rightMin[]' array from
// 2nd digit up to the last digit
for (var i = 1; i < n; i++) {
// if for the current digit, smaller
// right digit exists, then swap it
// with its smaller right digit and
// break
if (rightMin[i] != -1 && num[i] != num[rightMin[i]]) {
// performing the required
// swap operation
var tmp = num[i]
num[i]= num[rightMin[i]];
num[rightMin[i]] = tmp
break;
}
}
}
// required smallest number
return num.join('');
}
// Driver program to test above
var num = "9625635".split('');
document.write( "Smallest number: "
+ smallestNumber(num));
// This code is contributed by rrrtnx.
</script>
Producción
Smallest number: 2695635
Complejidad de tiempo: O(n) , donde n es el número total de dígitos.
Espacio Auxiliar: O(n) , donde n es el número total de dígitos.
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA