Dada una array arr[] de longitud N , la tarea es modificar la array dada reemplazando cada elemento de la array dada por su siguiente elemento más pequeño, si es posible. Imprima la array modificada como la respuesta requerida.
Ejemplos:
Entrada: arr[] = {8, 4, 6, 2, 3}
Salida: 4 2 4 2 3
Explicación: Las operaciones se pueden realizar de la siguiente manera:
- Para arr[0], arr[1] es el siguiente elemento más pequeño.
- Para arr[1], arr[3] es el siguiente elemento más pequeño.
- Para arr[2], arr[3] es el siguiente elemento más pequeño.
- Para arr[3], ningún elemento menor está presente después de él.
- Para arr[4], ningún elemento menor está presente después de él.
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 1 2 3 4 5
Enfoque ingenuo: el enfoque más simple es recorrer la array y, para cada elemento, recorrer los elementos restantes después de él y verificar si hay algún elemento más pequeño presente o no. Si lo encuentra, reduzca ese elemento por el primer elemento más pequeño obtenido.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
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 print the final array
// after reducing each array element
// by its next smaller element
void printFinalPrices(vector<int>& arr)
{
// Stores the resultant array
vector<int> ans;
// Traverse the array
for (int i = 0; i < arr.size(); i++) {
int flag = 1;
for (int j = i + 1; j < arr.size(); j++) {
// If a smaller element is found
if (arr[j] <= arr[i]) {
// Reduce current element by
// next smaller element
ans.push_back(arr[i] - arr[j]);
flag = 0;
break;
}
}
// If no smaller element is found
if (flag == 1)
ans.push_back(arr[i]);
}
// Print the answer
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
}
// Driver Code
int main()
{
// Given array
vector<int> arr = { 8, 4, 6, 2, 3 };
// Function Call
printFinalPrices(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the final array
// after reducing each array element
// by its next smaller element
static void printFinalPrices(int[] arr)
{
// Stores the resultant array
ArrayList<Integer> ans = new ArrayList<Integer>();
// Traverse the array
for(int i = 0; i < arr.length; i++)
{
int flag = 1;
for(int j = i + 1; j < arr.length; j++)
{
// If a smaller element is found
if (arr[j] <= arr[i])
{
// Reduce current element by
// next smaller element
ans.add(arr[i] - arr[j]);
flag = 0;
break;
}
}
// If no smaller element is found
if (flag == 1)
ans.add(arr[i]);
}
// Print the answer
for(int i = 0; i < ans.size(); i++)
System.out.print(ans.get(i) + " ");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = { 8, 4, 6, 2, 3 };
// Function Call
printFinalPrices(arr);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program for the above approach # Function to print the final array # after reducing each array element # by its next smaller element def printFinalarr(arr): # Stores resultant array ans = [] # Traverse the given array for i in range(len(arr)): flag = 1 for j in range(i + 1, len(arr)): # If a smaller element is found if arr[j] <= arr[i]: # Reduce current element by # next smaller element ans.append(arr[i] - arr[j]) flag = 0 break if flag: # If no smaller element is found ans.append(arr[i]) # Print the final array for k in range(len(ans)): print(ans[k], end =' ') # Driver Code if __name__ == '__main__': # Given array arr = [8, 4, 6, 2, 3] # Function call printFinalarr(arr)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to print the final array
// after reducing each array element
// by its next smaller element
static void printFinalPrices(int[] arr)
{
// Stores the resultant array
List<int> ans = new List<int>();
// Traverse the array
for(int i = 0; i < arr.Length; i++)
{
int flag = 1;
for(int j = i + 1; j < arr.Length; j++)
{
// If a smaller element is found
if (arr[j] <= arr[i])
{
// Reduce current element by
// next smaller element
ans.Add(arr[i] - arr[j]);
flag = 0;
break;
}
}
// If no smaller element is found
if (flag == 1)
ans.Add(arr[i]);
}
// Print the answer
for(int i = 0; i < ans.Count; i++)
Console.Write(ans[i] + " ");
}
// Driver code
static void Main()
{
// Given array
int[] arr = { 8, 4, 6, 2, 3 };
// Function Call
printFinalPrices(arr);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Js program for the above approach
// Function to print the final array
// after reducing each array element
// by its next smaller element
function printFinalPrices( arr)
{
// Stores the resultant array
let ans = [];
// Traverse the array
for (let i = 0; i < arr.length; i++) {
let flag = 1;
for (let j = i + 1; j < arr.length; j++) {
// If a smaller element is found
if (arr[j] <= arr[i]) {
// Reduce current element by
// next smaller element
ans.push(arr[i] - arr[j]);
flag = 0;
break;
}
}
// If no smaller element is found
if (flag == 1)
ans.push(arr[i]);
}
// Print the answer
for (let i = 0; i < ans.length; i++)
document.write(ans[i], " ");
}
// Driver Code
// Given array
let arr = [ 8, 4, 6, 2, 3 ];
// Function Call
printFinalPrices(arr);
</script>
Producción:
4 2 4 2 3
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la estructura de datos Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice una pila y una array ans[] de tamaño N para almacenar la array resultante.
- Recorre la array dada sobre los índices i = N – 1 a 0 .
- Si la pila está vacía , empuje el elemento actual arr[i] a la parte superior de la pila .
- De lo contrario, si el elemento actual es mayor que el elemento en la parte superior de la pila , empújelo hacia la pila y luego elimine elementos de la pila , hasta que la pila se vacíe o se encuentre un elemento menor o igual que arr[i] . Después de eso, si la pila no está vacía, establezca ans[i] = arr[i] – elemento superior de la pila y luego elimínelo de la pila.
- De lo contrario, elimine el elemento superior de la pila y establezca ans[i] igual al elemento superior de la pila y luego elimínelo de la pila.
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 print the final array
// after reducing each array element
// by its next smaller element
void printFinalPrices(vector<int>& arr)
{
// Initialize stack
stack<int> minStk;
// Array size
int n = arr.size();
// To store the corresponding element
vector<int> reduce(n, 0);
for (int i = n - 1; i >= 0; i--) {
// If stack is not empty
if (!minStk.empty()) {
// If top element is smaller
// than the current element
if (minStk.top() <= arr[i]) {
reduce[i] = minStk.top();
}
else {
// Keep popping until stack is empty
// or top element is greater than
// the current element
while (!minStk.empty()
&& (minStk.top() > arr[i])) {
minStk.pop();
}
// If stack is not empty
if (!minStk.empty()) {
reduce[i] = minStk.top();
}
}
}
// Push current element
minStk.push(arr[i]);
}
// Print the final array
for (int i = 0; i < n; i++)
cout << arr[i] - reduce[i] << " ";
}
// Driver Code
int main()
{
// Given array
vector<int> arr = { 8, 4, 6, 2, 3 };
// Function call
printFinalPrices(arr);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to print the final array
// after reducing each array element
// by its next smaller element
static void printFinalPrices(int[] arr)
{
// Initialize stack
Stack<Integer> minStk = new Stack<>();
// Array size
int n = arr.length;
// To store the corresponding element
int[] reduce = new int[n];
for(int i = n - 1; i >= 0; i--)
{
// If stack is not empty
if (!minStk.isEmpty())
{
// If top element is smaller
// than the current element
if (minStk.peek() <= arr[i])
{
reduce[i] = minStk.peek();
}
else
{
// Keep popping until stack is empty
// or top element is greater than
// the current element
while (!minStk.isEmpty() &&
(minStk.peek() > arr[i]))
{
minStk.pop();
}
// If stack is not empty
if (!minStk.isEmpty())
{
reduce[i] = minStk.peek();
}
}
}
// Push current element
minStk.add(arr[i]);
}
// Print the final array
for(int i = 0; i < n; i++)
System.out.print(arr[i] - reduce[i] + " ");
}
// Driver Code
public static void main(String[] args)
{
// Given array
int[] arr = { 8, 4, 6, 2, 3 };
// Function call
printFinalPrices(arr);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function to print the final array # after reducing each array element # by its next smaller element def printFinalPrices(arr): # Initialize stack minStk = [] # To store the corresponding element reduce = [0] * len(arr) for i in range(len(arr) - 1, -1, -1): # If stack is not empty if minStk: # If top element is smaller # than the current element if minStk[-1] <= arr[i]: reduce[i] = minStk[-1] else: # Keep popping until stack is empty # or top element is greater than # the current element while minStk and minStk[-1] > arr[i]: minStk.pop() if minStk: # Corresponding elements reduce[i] = minStk[-1] # Push current element minStk.append(arr[i]) # Final array for i in range(len(arr)): print(arr[i] - reduce[i], end =' ') # Driver Code if __name__ == '__main__': # Given array arr = [8, 4, 6, 2, 3] # Function Call printFinalPrices(arr)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to print the readonly array
// after reducing each array element
// by its next smaller element
static void printFinalPrices(int[] arr)
{
// Initialize stack
Stack<int> minStk = new Stack<int>();
// Array size
int n = arr.Length;
// To store the corresponding element
int[] reduce = new int[n];
for(int i = n - 1; i >= 0; i--)
{
// If stack is not empty
if (minStk.Count != 0)
{
// If top element is smaller
// than the current element
if (minStk.Peek() <= arr[i])
{
reduce[i] = minStk.Peek();
}
else
{
// Keep popping until stack is empty
// or top element is greater than
// the current element
while (minStk.Count != 0 &&
(minStk.Peek() > arr[i]))
{
minStk.Pop();
}
// If stack is not empty
if (minStk.Count != 0)
{
reduce[i] = minStk.Peek();
}
}
}
// Push current element
minStk.Push(arr[i]);
}
// Print the readonly array
for(int i = 0; i < n; i++)
Console.Write(arr[i] - reduce[i] + " ");
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int[] arr = { 8, 4, 6, 2, 3 };
// Function call
printFinalPrices(arr);
}
}
// This code contributed by shikhasingrajput
Javascript
<script>
// javascript program for the above approach
// Function to print the final array
// after reducing each array element
// by its next smaller element
function printFinalPrices(arr)
{
// Initialize stack
var minStk = []
// Array size
var n = arr.length;
var i;
// To store the corresponding element
var reduce = Array(n).fill(0);
for (i = n - 1; i >= 0; i--) {
// If stack is not empty
if (minStk.length>0) {
// If top element is smaller
// than the current element
if (minStk[minStk.length-1] <= arr[i]) {
reduce[i] = minStk[minStk.length-1];
}
else {
// Keep popping until stack is empty
// or top element is greater than
// the current element
while (minStk.length>0
&& (minStk[minStk.length-1] > arr[i])) {
minStk.pop();
}
// If stack is not empty
if (minStk.length>0) {
reduce[i] = minStk[minStk.length-1];
}
}
}
// Push current element
minStk.push(arr[i]);
}
// Print the final array
for (i = 0; i < n; i++)
document.write(arr[i] - reduce[i] + " ");
}
// Driver Code
// Given array
var arr = [8, 4, 6, 2, 3];
// Function call
printFinalPrices(arr);
// This code is contributed by ipg2016107.
</script>
Producción:
4 2 4 2 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Rohit_prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA