Dada una array arr[] de tamaño N , la tarea es encontrar la array final realizando repetidamente las siguientes operaciones si dos elementos de signos opuestos son adyacentes:
- Elimine los dos elementos con signo opuesto de la array e inserte el elemento que tenga el valor absoluto máximo junto con su signo.
- Si ambos elementos tienen el mismo valor absoluto, ambos se eliminarán de la array.
Ejemplos:
Entrada: arr[] = {10, -5, -8, 2, -5}
Salida: 10
Explicación:
en el índice 0: el elemento 10 tiene signo positivo.
En el Índice 1: -5 tiene un valor absoluto menor que 10. Reemplace ambos con 10.
En el Índice 2: -8 tiene un valor absoluto menor que 10. Reemplace ambos con 10.
En el Índice 3: 2 tiene signo positivo. Entonces estará en la array.
En el Índice 4: -5 tiene un valor absoluto mayor que 2. Reemplácelos a ambos con 5.
Ahora -5 tiene un valor absoluto menor que 10. Reemplácelos a ambos con 10.Entrada: arr[] = {5, -5, -2, -10}
Salida: -2 -10
Explicación: el primer y segundo elemento se descartan porque
ambos elementos tienen los mismos valores pero signo opuesto.
Los elementos 3 y 4 tienen el mismo signo. Entonces ambos estarán en la array.
Enfoque: El problema se puede resolver usando la siguiente idea:
En cualquier momento, también se pueden requerir los elementos anteriores, por lo que se puede usar una estructura de datos Stack para contener los elementos, y los elementos más pequeños se pueden extraer de manera eficiente de la pila debido a su propiedad de último en entrar, primero en salir.
Mire la siguiente ilustración para una mejor comprensión:
Considere la array arr[] = {10, -5, -8, 2, -5}.
Inicialmente, la pila está vacía, st = { }
En el índice 0: =
> arr[0] = 10
=> st = {}
=> Empuje 10 en la pila
=> La pila es st = {10}En el 1er índice:
=> arr[1] = -5
=> st = {10}
=> El elemento superior de la pila es positivo y arr[1] es negativo.
=> Como arr[1] tiene un valor absoluto menor, es decir, 5 que el elemento superior de la pila, por lo que no hay cambios en la pila.
=> La pila es st = {10}En el segundo índice:
=> arr[2] = -8
=> st = {10}
=> El elemento superior de la pila es positivo y arr[2] es negativo.
=> Como arr[2] tiene un valor absoluto menor, es decir, 8 que el elemento superior de la pila, por lo que no hay cambios en la pila.
=> La pila es st = {10}En el tercer índice:
=> arr[3] = 2
=> El elemento superior de la pila es positivo y arr[3] también es positivo.
=> Empuje 2 en la pila.
=> La pila es st = {10, 2}En el cuarto índice:
=> arr[4] = -5
=> st = {10, 2}
=> El elemento superior de la pila es positivo y arr[4] es negativo.
=> Como arr[4] tiene un valor absoluto mayor, es decir, 5 que el elemento superior de la pila, saque el elemento superior de la pila.
=> La pila cambia de st = {10, 2 } a st = {10}
=> Ahora nuevamente, el elemento superior de la pila es positivo y arr[4] es negativo.
=> arr[4] tiene un valor absoluto menor, es decir, 5 que el elemento superior. Así que no hay cambios en la pila.
=> La pila permanece st = {10}Los elementos que finalmente quedan en la pila son los elementos finales de la array.
Entonces, los elementos que quedan en la array son arr = {10}
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Declare una pila para contener los elementos de la array.
- Atraviese la array. Si el elemento es positivo, empújelo directamente a la pila.
- De lo contrario, si el arr actual [i] es negativo, entonces
- Intente extraer todos los elementos más pequeños de la pila que sean positivos , indicando que el elemento que tiene un valor absoluto más pequeño ha sido descartado.
- Si el elemento actual y la parte superior de la pila son iguales y la parte superior de la pila es positiva , salte de la pila, indicando que ambos elementos con valores iguales pero con el signo opuesto han sido descartados.
- Por último, si la pila está vacía o el último elemento es negativo, inserte el elemento arr[i] actual en la pila. Como todos los elementos restantes tendrán signo negativo.
- Finalmente, devuelva la pila, mostrando los elementos restantes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the remaining elements
vector<int> solve(vector<int>& arr)
{
// Stack to store elements
vector<int> st;
// Traverse entire array
for (auto element : arr) {
// If positive element,
// directly push
if (element >= 0)
st.push_back(element);
else {
// Pop all the smaller elements
// moving in the right direction
while (st.size() > 0 && st.back() >= 0
&& abs(element) > st.back())
st.pop_back();
// Top of stack and current
// element same value and top of
// stack moving in right direction
if (st.size() > 0 && st.back() >= 0
&& st.back() == abs(element))
st.pop_back();
// No more elements remaining or
// remaining elements
// moving in left direction
else if (st.size() == 0 || st.back() < 0)
st.push_back(element);
}
}
// Finally return stack
return st;
}
};
// Driver code
int main()
{
Solution obj;
vector<int> arr = { 5, -5, -2, -10 };
vector<int> ans = obj.solve(arr);
for (auto x : ans)
cout << x << " ";
return 0;
}
// This code is contributed by rakeshsahni
Java
import java.util.*;
import java.io.*;
class GFG{
// Function to find remaining element
public static ArrayList<Integer> solve(ArrayList<Integer> arr){
// Stack to store elements
ArrayList<Integer> st = new ArrayList<Integer>();
// Traverse entire array
for(Integer element: arr){
// If positive element,
// directly push
if(element >= 0)
{
st.add(element);
}
else
{
// Pop all the smaller elements
// moving in the right direction
while(st.size()>0 && st.get(st.size()-1) >= 0 && Math.abs(element) > st.get(st.size()-1)){
st.remove(st.size()-1);
}
// Top of stack and current
// element same value and top of
// stack moving in right direction
if (st.size() > 0 && st.get(st.size()-1) >= 0 && st.get(st.size()-1) == Math.abs(element)){
st.remove(st.size()-1);
}
// No more elements remaining or
// remaining elements
// moving in left direction
else if (st.size() == 0 || st.get(st.size()-1) < 0){
st.add(element);
}
}
}
// Finally return stack
return st;
}
// Driver code
public static void main(String args[])
{
// Size of array
int N = 5;
ArrayList<Integer> arr = new ArrayList<Integer>();
arr.add(5);
arr.add(-5);
arr.add(-2);
arr.add(-10);
ArrayList<Integer> ans = solve(arr);
for(int i=0 ; i<ans.size() ; i++){
System.out.print(ans.get(i) + " ");
}
}
}
// This code is contributed by subhamgoyal2014.
Python3
# Python code to implement the approach class Solution: # Function to find the remaining elements def solve(self, arr): # Stack to store elements stack = [] # Traverse entire array for element in arr: # If positive element, # directly push if (element >= 0): stack.append(element) else: # Pop all the smaller elements # moving in the right direction while(stack and stack[-1] >= 0 \ and abs(element) > stack[-1]): stack.pop() # Top of stack and current # element same value and top of # stack moving in right direction if (stack and stack[-1] >= 0 \ and stack[-1] == abs(element)): stack.pop() # No more elements remaining or # remaining elements # moving in left direction elif(len(stack) == 0 \ or stack[-1] < 0): stack.append(element) # Finally return stack return stack # Driver code if __name__ == '__main__': obj = Solution() arr = [5, -5, -2, -10] ans = obj.solve(arr) for x in ans: print(x, end = " ")
C#
using System;
using System.Collections.Generic;
public class GFG{
// Function to find remaining element
public static List<int> solve(List<int> arr){
// Stack to store elements
List<int> st = new List<int>();
// Traverse entire array
foreach(int element in arr){
// If positive element,
// directly push
if(element >= 0)
{
st.Add(element);
}
else
{
// Pop all the smaller elements
// moving in the right direction
while(st.Count>0 && st[st.Count-1] >= 0 && Math.Abs(element) > st[st.Count-1]){
st.RemoveAt(st.Count-1);
}
// Top of stack and current
// element same value and top of
// stack moving in right direction
if (st.Count > 0 && st[st.Count-1] >= 0 && st[st.Count-1] == Math.Abs(element)){
st.RemoveAt(st.Count-1);
}
// No more elements remaining or
// remaining elements
// moving in left direction
else if (st.Count == 0 || st[st.Count-1] < 0){
st.Add(element);
}
}
}
// Finally return stack
return st;
}
// Driver code
public static void Main(String []args)
{
// Size of array
int N = 5;
List<int> arr = new List<int>();
arr.Add(5);
arr.Add(-5);
arr.Add(-2);
arr.Add(-10);
List<int> ans = solve(arr);
for(int i = 0; i < ans.Count; i++){
Console.Write(ans[i] + " ");
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to implement the approach
class Solution
{
// Function to find the remaining elements
solve(arr)
{
// Stack to store elements
let st = [];
// Traverse entire array
for (let element of arr) {
// If positive element,
// directly push
if (element >= 0)
st.push(element);
else
{
// Pop all the smaller elements
// moving in the right direction
while (st.length > 0 && st[st.length-1] >= 0
&& Math.abs(element) > st[st.length-1])
st.pop();
// Top of stack and current
// element same value and top of
// stack moving in right direction
if (st.length > 0 && st[st.length-1] >= 0
&& st[st.length-1] == Math.abs(element))
st.pop();
// No more elements remaining or
// remaining elements
// moving in left direction
else if (st.length == 0 || st[st.length-1] < 0)
st.push(element);
}
}
// Finally return stack
return st;
}
}
// Driver code
let obj = new Solution();
let arr = [ 5, -5, -2, -10 ];
let ans = obj.solve(arr);
for (let x of ans)
document.write(x," ");
// This code is contributed by shinjanpatra
</script>
-2 -10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)