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 grande posible. El número podría ser muy grande, por lo que se puede usar un tipo de string para almacenar el número.
Ejemplos:
Input : n = 8725634 Output : 8765234 Swapped the digits 2 and 6. Input : n = 54321 Output : 54321 No swapping of digits required.
Cree una array rightMax[] . rightMax[i] contiene el índice del dígito mayor que está en el lado derecho de num[i] y también mayor que num[i] . Si no existe tal dígito, entonces rightMax[i] = -1. Ahora, recorra la array rightMax[] de i = 0 a n-1 (donde n es el número total de dígitos en num ), y busque el primer elemento que tenga rightMax[i] != -1. Realice la operación swap(num[i], num[rightMax[i]]) y rompa.
C++
// C++ implementation to form the largest number
// by applying atmost one swap operation
#include <bits/stdc++.h>
using namespace std;
// function to form the largest number by
// applying atmost one swap operation
string largestNumber(string num)
{
int n = num.size();
int rightMax[n], right;
// for the rightmost digit, there
// will be no greater right digit
rightMax[n - 1] = -1;
// index of the greatest 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 >= 0; i--) {
// if 'num[i]' is less than the greatest digit
// encountered so far
if (num[i] < num[right])
rightMax[i] = right;
// else
else {
// there is no greater right digit
// for 'num[i]'
rightMax[i] = -1;
// update 'right' index
right = i;
}
}
// traverse the 'rightMax[]' array from left to right
for (int i = 0; i < n; i++) {
// if for the current digit, greater right digit exists
// then swap it with its greater right digit and break
if (rightMax[i] != -1) {
// performing the required swap operation
swap(num[i], num[rightMax[i]]);
break;
}
}
// required largest number
return num;
}
// Driver program to test above
int main()
{
string num = "8725634";
cout << "Largest number:"
<< largestNumber(num);
return 0;
}
Java
//Java implementation to form the largest number
//by applying atmost one swap operation
public class GFG
{
// function to form the largest number by
// applying atmost one swap operation
static String largestNumber(String num)
{
int n = num.length();
int right;
int rightMax[] = new int[n];
// for the rightmost digit, there
// will be no greater right digit
rightMax[n - 1] = -1;
// index of the greatest 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 - 1; i >= 0 ; i--)
{
// if 'num.charAt(i)' is less than the
// greatest digit encountered so far
if (num.charAt(i) < num.charAt(right))
rightMax[i] = right;
else
{
// there is no greater right digit
// for 'num.charAt(i)'
rightMax[i] = -1;
// update 'right' index
right = i;
}
}
// traverse the 'rightMax[]' array from
// left to right
for (int i = 0; i < n; i++)
{
// if for the current digit, greater
// right digit exists then swap it
// with its greater right digit and break
if (rightMax[i] != -1)
{
// performing the required swap operation
num = swap(num,i,rightMax[i]);
break;
}
}
// required largest number
return num;
}
// Utility method to swap two characters
// in a String
static String swap(String num, int i, int j)
{
StringBuilder sb= new StringBuilder(num);
sb.setCharAt(i, num.charAt(j));
sb.setCharAt(j, num.charAt(i));
return sb.toString();
}
//Driver Function to test above Function
public static void main(String[] args)
{
String num = "8725634";
System.out.println("Largest Number : " +
largestNumber(num));
}
}
//This code is contributed by Sumit Ghosh
Python3
# Python implementation to form the largest number
# by applying atmost one swap operation
# function to form the largest number by
# applying atmost one swap operation
def largestNumber(num):
n = len(num)
rightMax = [0 for i in range(n)]
# for the rightmost digit, there
# will be no greater right digit
rightMax[n - 1] = -1
# index of the greatest 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
i = n - 2
while i >= 0:
# if 'num[i]' is less than the greatest digit
# encountered so far
if (num[i] < num[right]):
rightMax[i] = right
# else
else:
# there is no greater right digit
# for 'num[i]'
rightMax[i] = -1
# update 'right' index
right = i
i -= 1
# traverse the 'rightMax[]' array from left to right
for i in range(n):
# if for the current digit, greater right digit exists
# then swap it with its greater right digit and break
if (rightMax[i] != -1):
# performing the required swap operation
t = num[i]
num[i] = num[rightMax[i]]
num[rightMax[i]] = t
break
# required largest number
return num
# Driver program to test above
num = "8725634"
li = [i for i in num]
print("Largest number: ")
li = largestNumber(li)
for i in li:
print(i,end=" ")
print()
#This code is contributed by Sachin Bisht
C#
// C# implementation to form the largest number
// by applying atmost one swap operation
using System;
using System.Text;
public class GFG
{
// function to form the largest number by
// applying atmost one swap operation
static String largestNumber(String num)
{
int n = num.Length;
int right;
int[] rightMax = new int[n];
// for the rightmost digit, there
// will be no greater right digit
rightMax[n - 1] = -1;
// index of the greatest 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 - 1; i >= 0 ; i--)
{
// if 'num.charAt(i)' is less than the
// greatest digit encountered so far
if (num[i] < num[right])
rightMax[i] = right;
else
{
// there is no greater right digit
// for 'num.charAt(i)'
rightMax[i] = -1;
// update 'right' index
right = i;
}
}
// traverse the 'rightMax[]' array from
// left to right
for (int i = 0; i < n; i++)
{
// if for the current digit, greater
// right digit exists then swap it
// with its greater right digit and break
if (rightMax[i] != -1)
{
// performing the required swap operation
num = swap(num,i,rightMax[i]);
break;
}
}
// required largest number
return num;
}
// Utility method to swap two characters
// in a String
static String swap(String num, int i, int j)
{
StringBuilder sb= new StringBuilder(num);
sb[i]=num[j];
sb[j]=num[i];
return sb.ToString();
}
//Driver Function to test above Function
public static void Main()
{
String num = "8725634";
Console.WriteLine("Largest Number : " +largestNumber(num));
}
}
//This code is contributed by mits
PHP
<?php
// PHP implementation to form the
// largest number by applying atmost
// one swap operation
// function to form the largest number by
// applying atmost one swap operation
function largestNumber($num)
{
$n = strlen($num);
$rightMax[$n] = array(0);
$right;
// for the rightmost digit, there
// will be no greater right digit
$rightMax[$n - 1] = -1;
// index of the greatest 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 >= 0; $i--)
{
// if 'num[i]' is less than the
// greatest digit encountered so far
if ($num[$i] < $num[$right])
$rightMax[$i] = $right;
// else
else
{
// there is no greater right
// digit for 'num[i]'
$rightMax[$i] = -1;
// update 'right' index
$right = $i;
}
}
// traverse the 'rightMax[]'
// array from left to right
for ($i = 0; $i < $n; $i++)
{
// if for the current digit, greater
// right digit exists then swap it
// with its greater right digit and break
if ($rightMax[$i] != -1)
{
// performing the required swap operation
list($num[$i],
$num[$rightMax[$i]]) = array($num[$rightMax[$i]],
$num[$i]);
break;
}
}
// required largest number
return $num;
}
// Driver Code
$num = "8725634";
echo "Largest number: ",
largestNumber($num);
// This code is contributed by jit_t
?>
Javascript
<script>
// Javascript implementation to form the largest number
// by applying atmost one swap operation
// function to form the largest number by
// applying atmost one swap operation
function largestNumber(num)
{
var n = num.length;
var rightMax = Array(n), right;
// for the rightmost digit, there
// will be no greater right digit
rightMax[n - 1] = -1;
// index of the greatest 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 >= 0; i--) {
// if 'num[i]' is less than the greatest digit
// encountered so far
if (num[i] < num[right])
rightMax[i] = right;
// else
else {
// there is no greater right digit
// for 'num[i]'
rightMax[i] = -1;
// update 'right' index
right = i;
}
}
// traverse the 'rightMax[]' array from left to right
for (var i = 0; i < n; i++) {
// if for the current digit, greater right digit exists
// then swap it with its greater right digit and break
if (rightMax[i] != -1) {
// performing the required swap operation
var tmp = num[i];
num[i] = num[rightMax[i]];
num[rightMax[i]] = tmp
break;
}
}
// required largest number
return num.join('');
}
// Driver program to test above
var num = "8725634".split('');
document.write( "Largest number:"
+ largestNumber(num));
// This code is contributed by rrrtnx.
</script>
Producción:
Largest number: 8765234
Complejidad temporal: 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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