Dada una lista de N enteros distintos y una lista de N-1 signos de desigualdad, la tarea es insertar los enteros entre los signos de desigualdad, de modo que la desigualdad final formada siempre sea verdadera.
Nota: No se debe cambiar el orden de los signos de desigualdad.
Ejemplos:
Entrada: Enteros: [ 2, 5, 1, 0 ], Signos: [ <, >, < ]
Salida: 0 < 5 > 1 < 2
Explicación:
La desigualdad formada es consistente y válida.Entrada: Enteros: [ 8, 34, 25, 1, -5, 10], Signos: [ >, >, <, <, > ]
Salida: 34 > 25 > -5 < 1 < 10 > 8
Explicación:
La desigualdad formada es consistente y válida.
Enfoque: La lista de símbolos de desigualdad puede contener símbolos en cualquier orden. Entonces, para obtener una desigualdad consistente, coloque el entero más pequeño que queda en la array antes de cada símbolo < y el entero más grande que queda antes de cada símbolo > . En base a esta idea, a continuación se detallan los pasos:
- Ordena la lista de números enteros en orden ascendente .
- Mantenga dos variables, digamos low y high , apuntando al primer y último índice de la lista de enteros.
- Iterar sobre la lista de símbolos de desigualdad. Si el símbolo actual es menor, agregue el número entero apuntado por bajo antes de < e incremente bajo para apuntar al siguiente índice. Si el símbolo actual es mayor, agregue el número entero señalado por high antes de > y disminuya high para señalar el índice anterior.
- Finalmente, agregue el elemento restante a la última posición.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.util.Arrays;
public class PlacingNumbers {
// Function to place the integers
// in between the inequality signs
static String
formAnInequality(int[] integers,
char[] inequalities)
{
// Sort the integers array and
// set the index of smallest
// and largest element
Arrays.sort(integers);
int lowerIndex = 0;
int higherIndex = integers.length - 1;
StringBuilder sb = new StringBuilder();
// Iterate over the inequalities
for (char ch : inequalities) {
// Append the necessary
// integers per symbol
if (ch == '<') {
sb.append(" "
+ integers[lowerIndex++]
+ " "
+ ch);
}
else {
sb.append(" "
+ integers[higherIndex--]
+ " "
+ ch);
}
}
// Add the final integer
sb.append(" " + integers[lowerIndex]);
// Return the answer
return sb.toString();
}
// Driver Code
public static void main(String[] args)
{
// Given List of Integers
int[] integers = { 2, 5, 1, 0 };
// Given list of inequalities
char[] inequalities = { '<', '>', '<' };
// Function Call
String output
= formAnInequality(integers,
inequalities);
// Print the output
System.out.println(output);
}
}
Python3
# Python3 program for
# the above approach
# Function to place the integers
# in between the inequality signs
def formAnInequality(integers,
inequalities):
# Sort the integers array and
# set the index of smallest
# and largest element
integers.sort()
lowerIndex = 0
higherIndex = len(integers) - 1
sb = ""
# Iterate over the inequalities
for ch in inequalities:
# Append the necessary
# integers per symbol
if (ch == '<'):
sb += (" " + chr(integers[lowerIndex]) +
" " + ch)
lowerIndex += 1
else:
sb += (" " + chr(integers[higherIndex]) +
" " + ch)
higherIndex -= 1
# Add the final integer
sb += (" " + chr(integers[lowerIndex]))
# Return the answer
return sb
# Driver Code
if __name__ == "__main__":
# Given List of Integers
integers = [2, 5, 1, 0]
# Given list of inequalities
inequalities = ['<', '>', '<']
# Function Call
output = formAnInequality(integers,
inequalities)
# Print the output
print(output)
# This code is contributed by Chitranayal
C#
// C# program for the above approach
using System;
using System.Text;
class GFG{
// Function to place the integers
// in between the inequality signs
static String
formAnInequality(int[] integers,
char[] inequalities)
{
// Sort the integers array and
// set the index of smallest
// and largest element
Array.Sort(integers);
int lowerIndex = 0;
int higherIndex = integers.Length - 1;
StringBuilder sb = new StringBuilder();
// Iterate over the inequalities
foreach(char ch in inequalities)
{
// Append the necessary
// integers per symbol
if (ch == '<')
{
sb.Append(" " + integers[lowerIndex++] +
" " + ch);
}
else
{
sb.Append(" " + integers[higherIndex--] +
" " + ch);
}
}
// Add the readonly integer
sb.Append(" " + integers[lowerIndex]);
// Return the answer
return sb.ToString();
}
// Driver Code
public static void Main(String[] args)
{
// Given List of ints
int[] integers = { 2, 5, 1, 0 };
// Given list of inequalities
char[] inequalities = { '<', '>', '<' };
// Function call
String output = formAnInequality(integers,
inequalities);
// Print the output
Console.WriteLine(output);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to place the integers
// in between the inequality signs
function formAnInequality(integers, inequalities)
{
// Sort the integers array and
// set the index of smallest
// and largest element
(integers).sort(function(a, b){return a - b;});
let lowerIndex = 0;
let higherIndex = integers.length - 1;
let sb = "";
// Iterate over the inequalities
for(let ch = 0; ch < inequalities.length; ch++)
{
// Append the necessary
// integers per symbol
if (inequalities[ch] == '<')
{
sb += " " + (integers[lowerIndex++]) +
" " + inequalities[ch];
}
else
{
sb += " " + (integers[higherIndex--]) +
" " + inequalities[ch];
}
}
// Add the final integer
sb += " " + (integers[lowerIndex]);
// Return the answer
return sb;
}
// Driver Code
// Given List of Integers
let integers = [ 2, 5, 1, 0 ];
// Given list of inequalities
let inequalities = [ '<', '>', '<' ];
// Function Call
let output = formAnInequality(
integers, inequalities);
// Print the output
document.write(output);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
0 < 5 > 1 < 2
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por CharchitKapoor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA