Dada una array enteros[] de enteros de tamaño N . Encuentre la array de salida resultante después de realizar algunas operaciones:
- Si el (i-1) ésimo elemento es positivo y el i ésimo elemento es negativo entonces:
- Si el valor absoluto de (i) th es mayor que (it)th , elimine todos los elementos positivos contiguos de la izquierda que tengan un valor absoluto menor que ith .
- Si el absoluto de (i) th es menor que (it) th , elimine este elemento.
- Si el absoluto de (i) th es igual a (i-1) th , elimine ambos elementos.
Ejemplos:
Entrada: enteros[] = {3, -2, 4}
Salida: 3 4
Explicación: El primer número cancelará el segundo número.
Por lo tanto, la array de salida será {3,4}.Entrada: enteros[] = {-2, -1, 1, 2}
Salida: -2 -1 1 2
Explicación: después de un número positivo, no se suma un número negativo.
Entonces, cada número estaría presente en la array de salida
Enfoque: Ignorar números del mismo signo independientemente de su magnitud. Entonces, el único caso que debemos considerar es cuando el elemento anterior es de magnitud positiva y el siguiente elemento es de magnitud negativa. Podemos usar stack para simular el problema. Siga los pasos a continuación para resolver el problema:
- Inicialice la pila s[].
- Itere sobre el rango [0, N) usando la variable i y realice las siguientes tareas:
- Si integers[i] es mayor que 0 o s[] está vacío, inserte integers[i] en la pila s[] .
- De lo contrario, recorra un ciclo while hasta que s no esté vacío y s.top() sea mayor que 0 y s.top() sea menor que abs(integers[i]) y realice las siguientes tareas:
- Extraiga el elemento de la pila s[].
- Si s no está vacío y s.top() es igual a abs(integers[i]) , entonces extraiga de la pila s[].
- De lo contrario, si s[] está vacío o s.top() es menor que 0 , inserte enteros[i] en la pila s[].
- Inicialice el vector res[s.size()] para almacenar el resultado.
- Iterar sobre el rango [s.size()-1, 0] usando la variable i y realizar las siguientes tareas:
- Establezca res[i] como s.top() y extraiga de la pila s[].
- Después de realizar los pasos anteriores, imprima el valor de res[] 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 remaining numbers
vector<int> remainingNumbers(vector<int>&
integers)
{
// Size of the array
int n = integers.size();
// Initialize the stack
stack<int> s;
// Traverse the array
for (int i = 0; i < n; i++) {
if (integers[i] > 0 || s.empty()) {
s.push(integers[i]);
}
else {
while (!s.empty() and s.top() > 0
and s.top() <
abs(integers[i])) {
s.pop();
}
if (!s.empty()
and s.top() ==
abs(integers[i])) {
s.pop();
}
else if (s.empty() ||
s.top() < 0) {
s.push(integers[i]);
}
}
}
// Finally we are returning the elements
// which remains in the stack.
// we have to return them in reverse order.
vector<int> res(s.size());
for (int i = (int)s.size() - 1; i >= 0;
i--) {
res[i] = s.top();
s.pop();
}
return res;
}
// Driver Code
int main()
{
vector<int> integers = { 3, -2, 4 };
vector<int> ans =
remainingNumbers(integers);
for (int x : ans) {
cout << x << " ";
}
return 0;
}
Java
// Java program for the above approach
import java.util.Stack;
class GFG {
// Function to find the remaining numbers
static int[] remainingNumbers(int[] integers)
{
// Size of the array
int n = integers.length;
// Initialize the stack
Stack<Integer> s = new Stack<Integer>();
// Traverse the array
for (int i = 0; i < n; i++) {
if (integers[i] > 0 || s.empty()) {
s.push(integers[i]);
}
else {
while (!s.empty() && s.peek() > 0
&& s.peek()
< Math.abs(integers[i])) {
s.pop();
}
if (!s.empty()
&& s.peek() == Math.abs(integers[i])) {
s.pop();
}
else if (s.empty() || s.peek() < 0) {
s.push(integers[i]);
}
}
}
// Finally we are returning the elements
// which remains in the stack.
// we have to return them in reverse order.
int[] res = new int[s.size()];
for (int i = s.size() - 1; i >= 0; i--) {
res[i] = s.peek();
s.pop();
}
return res;
}
// Driver Code
public static void main(String args[])
{
int[] integers = { 3, -2, 4 };
int[] ans = remainingNumbers(integers);
for (int x : ans) {
System.out.print(x + " ");
}
}
}
// This code is contributed by Lovely Jain
Python3
# python3 program for the above approach # Function to find the remaining numbers def remainingNumbers(integers): # Size of the array n = len(integers) # Initialize the stack s = [] # Traverse the array for i in range(0, n): if (integers[i] > 0 or len(s) == 0): s.append(integers[i]) else: while (len(s) != 0 and s[len(s) - 1] > 0 and s[len(s) - 1] < abs(integers[i])): s.pop() if (len(s) != 0 and s[len(s) - 1] == abs(integers[i])): s.pop() elif (len(s) == 0 or s[len(s) - 1] < 0): s.append(integers[i]) # Finally we are returning the elements # which remains in the stack. # we have to return them in reverse order. res = [0 for _ in range(len(s))] for i in range(len(s) - 1, -1, -1): res[i] = s[len(s) - 1] s.pop() return res # Driver Code if __name__ == "__main__": integers = [3, -2, 4] ans = remainingNumbers(integers) for x in ans: print(x, end=" ") # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the remaining numbers
static List<int> remainingNumbers(List<int> integers)
{
// Size of the array
int n = integers.Count;
// Initialize the stack
Stack<int> s = new Stack<int>();
// Traverse the array
for (int i = 0; i < n; i++) {
if (integers[i] > 0 || s.Count == 0) {
s.Push(integers[i]);
}
else {
while (s.Count != 0 && s.Peek() > 0
&& s.Peek()
< Math.Abs(integers[i])) {
s.Pop();
}
if (s.Count != 0
&& s.Peek() == Math.Abs(integers[i])) {
s.Pop();
}
else if (s.Count == 0 || s.Peek() < 0) {
s.Push(integers[i]);
}
}
}
// Finally we are returning the elements
// which remains in the stack.
// we have to return them in reverse order.
List<int> res = new List<int>(new int [s.Count]);
for (int i = (int)s.Count - 1; i >= 0; i--) {
res[i] = s.Peek();
s.Pop();
}
return res;
}
// Driver Code
public static void Main()
{
List<int> integers = new List<int>() { 3, -2, 4 };
List<int> ans = remainingNumbers(integers);
foreach(int x in ans) { Console.Write(x + " "); }
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to find the remaining numbers
function remainingNumbers(
integers) {
// Size of the array
let n = integers.length;
// Initialize the stack
let s = [];
// Traverse the array
for (let i = 0; i < n; i++) {
if (integers[i] > 0 || s.length == 0) {
s.push(integers[i]);
}
else {
while (s.length != 0 && s[s.length - 1] > 0
&& s[s.length - 1] <
Math.abs(integers[i])) {
s.pop();
}
if (s.length != 0
&& s[s.length - 1] ==
Math.abs(integers[i])) {
s.pop();
}
else if (s.length == 0 ||
s[s.length - 1] < 0) {
s.push(integers[i]);
}
}
}
// Finally we are returning the elements
// which remains in the stack.
// we have to return them in reverse order.
let res = new Array(s.length);
for (let i = s.length - 1; i >= 0;
i--) {
res[i] = s[s.length - 1];
s.pop();
}
return res;
}
// Driver Code
let integers = [3, -2, 4];
let ans =
remainingNumbers(integers);
for (let x of ans) {
document.write(x + " ");
}
// This code is contributed by Potta Lokesh
</script>
Producción
3 4
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prasanna1995 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA