El valor mayor o igual más cercano en el lado izquierdo para cada elemento en la array

Dada una array de enteros, encuentre el más cercano (sin considerar la distancia, sino el valor) mayor o el mismo valor a la izquierda de cada elemento. Si un elemento no tiene un valor mayor o igual en el lado izquierdo, imprima -1.

Ejemplos:  

Entrada: arr[] = {10, 5, 11, 6, 20, 12} 
Salida: -1, 10, -1, 10, -1, 20 
El primer elemento no tiene nada en el lado izquierdo, por lo que la respuesta para el primero es -1. 
Segundo, el elemento 5 tiene 10 a la izquierda, por lo que la respuesta es 10. 
El tercer elemento 11 no tiene nada mayor ni igual, por lo que la respuesta es -1. 
El cuarto elemento 6 tiene 10 como valor de cierre sabio, por lo que la respuesta es 10 
De manera similar, obtenemos valores para los elementos quinto y sexto.

Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento elegido, nos desplazamos hacia la izquierda y encontramos el elemento mayor más cercano (en términos de valor). La complejidad temporal de esta solución es O(n*n)

C++

#include <bits/stdc++.h>
using namespace std;
 
// function for ceiling in left side for every element in an
// array
void printPrevGreater(int arr[], int n)
{
    cout << "-1"
         << " "; // for first element
    for (int i = 1; i < n; i++) {
        int diff = INT_MAX;
        for (int j = 0; j < i;
             j++) // traverse left side to i-th element
        {
            if (arr[j] >= arr[i])
                diff = min(diff, arr[j] - arr[i]);
        }
        if (diff == INT_MAX)
            cout << "-1"
                 << " "; // if not found at left side
        else
            cout << arr[i] + diff << " ";
    }
}
 
// Driver code
int main()
{
    int arr[] = { 10, 5, 11, 10, 20, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printPrevGreater(arr, n);
    return 0;
}
 
// This code is contributed by
// @itsrahulhere_

Java

import java.util.*;
class GFG {
 
  // function for ceiling in left side for every element in an
  // array
  static void printPrevGreater(int arr[], int n) {
    System.out.print("-1" + " "); // for first element
    for (int i = 1; i < n; i++) {
      int diff = Integer.MAX_VALUE;
      for (int j = 0; j < i; j++) // traverse left side to i-th element
      {
        if (arr[j] >= arr[i])
          diff = Math.min(diff, arr[j] - arr[i]);
      }
      if (diff == Integer.MAX_VALUE)
        System.out.print("-1" + " "); // if not found at left side
      else
        System.out.print(arr[i] + diff + " ");
    }
  }
 
  // Driver code
  public static void main(String[] args) {
    int arr[] = { 10, 5, 11, 10, 20, 12 };
    int n = arr.length;
    printPrevGreater(arr, n);
  }
}
 
// This code is contributed by Rajput-Ji

Python3

import sys
 
# function for ceiling in left side for every element in an
# array
def printPrevGreater(arr,n):
 
    print("-1",end = ' ')  # for first element
    for i in range(1,n):
        diff = sys.maxsize
        for j in range(i): # traverse left side to i-th element
 
            if (arr[j] >= arr[i]):
                diff = min(diff, arr[j] - arr[i])
        if diff == sys.maxsize :
            print("-1",end = " ") # if not found at left side
        else :
            print(arr[i] + diff ,end = ' ')
 
# Driver code
arr = [ 10, 5, 11, 10, 20, 12 ]
n = len(arr)
printPrevGreater(arr, n)
 
# This code is contributed by shinjanpatra

C#

using System;
 
public class GFG {
 
  // function for ceiling in left side for every element in an
  // array
  static void printPrevGreater(int []arr, int n) {
    Console.Write("-1" + " "); // for first element
    for (int i = 1; i < n; i++) {
      int diff = int.MaxValue;
      for (int j = 0; j < i; j++) // traverse left side to i-th element
      {
        if (arr[j] >= arr[i])
          diff = Math.Min(diff, arr[j] - arr[i]);
      }
      if (diff == int.MaxValue)
        Console.Write("-1" + " "); // if not found at left side
      else
        Console.Write(arr[i] + diff + " ");
    }
  }
 
  // Driver code
  public static void Main(String[] args) {
    int []arr = { 10, 5, 11, 10, 20, 12 };
    int n = arr.Length;
    printPrevGreater(arr, n);
  }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
    // function for ceiling in left side for every element in an
    // array
    function printPrevGreater(arr , n) {
        document.write("-1" + " "); // for first element
        for (i = 1; i < n; i++) {
            var diff = Number.MAX_VALUE;
            for (j = 0; j < i; j++) // traverse left side to i-th element
            {
                if (arr[j] >= arr[i])
                    diff = Math.min(diff, arr[j] - arr[i]);
            }
            if (diff == Number.MAX_VALUE)
                document.write("-1" + " "); // if not found at left side
            else
                document.write(arr[i] + diff + " ");
        }
    }
 
    // Driver code
     
        var arr = [ 10, 5, 11, 10, 20, 12 ];
        var n = arr.length;
        printPrevGreater(arr, n);
 
// This code is contributed by Rajput-Ji
</script>

Producción: 

-1 10 -1 10 -1 20

Complejidad temporal: O(n * n)
Espacio auxiliar: O(1) 

Una solución eficiente es usar Self-Balancing BST (Implementado como se establece en C++ y TreeSet en Java). En un BST de autoequilibrio, podemos realizar operaciones tanto de inserción como más cercanas en tiempo O (Log n).
Usamos lower_bound() en C++ para encontrar el elemento mayor más cercano. Esta función funciona en el tiempo de inicio de sesión para un conjunto. 

C++

// C++ implementation of efficient algorithm to find
// greater or same element on left side
#include <iostream>
#include <set>
using namespace std;
 
// Prints greater elements on left side of every element
void printPrevGreater(int arr[], int n)
{
    set<int> s;
    for (int i = 0; i < n; i++) {
 
        // First search in set
        auto it = s.lower_bound(arr[i]);
        if (it == s.end()) // If no greater found
            cout << "-1"
                 << " ";
        else
            cout << *it << " ";
 
        // Then insert
        s.insert(arr[i]);
    }
}
 
/* Driver program to test insertion sort */
int main()
{
    int arr[] = { 10, 5, 11, 10, 20, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printPrevGreater(arr, n);
    return 0;
}

Java

// Java implementation of efficient algorithm
// to find greater or same element on left side
import java.util.TreeSet;
 
class GFG {
 
    // Prints greater elements on left side
    // of every element
    static void printPrevGreater(int[] arr, int n)
    {
        TreeSet<Integer> ts = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            Integer c = ts.ceiling(arr[i]);
            if (c == null) // If no greater found
                System.out.print(-1 + " ");
            else
                System.out.print(c + " ");
 
            // Then insert
            ts.add(arr[i]);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 10, 5, 11, 10, 20, 12 };
        int n = arr.length;
        printPrevGreater(arr, n);
    }
}
 
// This code is contributed by
// sanjeev2552

Python3

# Python3 implementation of efficient algorithm
# to find greater or same element on left side
 
# Prints greater elements
# on left side of every element
def printPrevGreater(arr, n):
 
    s = set()
    for i in range(0, n):
 
        # First search in set
        it = [x for x in s if x >= arr[i]]
        if len(it) == 0: # If no greater found
            print("-1", end = " ")
        else:                
            print(min(it), end = " ")        
 
        # Then insert
        s.add(arr[i])
 
# Driver Code
if __name__ == "__main__":
 
    arr = [10, 5, 11, 10, 20, 12]
    n = len(arr)
    printPrevGreater(arr, n)
     
# This code is contributed by Rituraj Jain

C#

// C# implementation of efficient algorithm
// to find greater or same element on left side
using System;
using System.Collections.Generic;
 
class GFG {
 
    // To get the minimum value
    static int minimum(SortedSet<int> ss)
    {
        int min = int.MaxValue;
 
        foreach(int i in ss) if (i < min)
            min = i;
 
        return min;
    }
 
    // Prints greater elements on left side
    // of every element
    static void printPrevGreater(int[] arr, int n)
    {
        SortedSet<int> s = new SortedSet<int>();
 
        for (int i = 0; i < n; i++) {
            SortedSet<int> ss = new SortedSet<int>();
 
            // First search in set
            foreach(int x in s) if (x >= arr[i])
                ss.Add(x);
 
            if (ss.Count == 0) // If no greater found
                Console.Write(-1 + " ");
            else
                Console.Write(minimum(ss) + " ");
 
            // Then insert
            s.Add(arr[i]);
        }
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        int[] arr = { 10, 5, 11, 10, 20, 12 };
        int n = arr.Length;
        printPrevGreater(arr, n);
    }
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
  
 
// Javascript implementation of efficient algorithm to find
// greater or same element on left side
 
// To get the minimum value
function minimum(ss)
{
    var min = 1000000000;
    ss.forEach(i => {
        if (i < min)
            min = i;
    });
    return min;
}
// Prints greater elements on left side of every element
function printPrevGreater(arr, n)
{
    var s = new Set();
    for (var i = 0; i < n; i++) {
 
        var ss = new Set();
 
         // First search in set
         s.forEach(x => {
                if(x >= arr[i])
                    ss.add(x);
         });
          
            if (ss.size == 0) // If no greater found
                document.write(-1 + " ");
            else
                document.write(minimum(ss) + " ");
 
        // Then insert
        s.add(arr[i]);
    }
}
 
/* Driver program to test insertion sort */
var arr = [10, 5, 11, 10, 20, 12];
var n = arr.length;
printPrevGreater(arr, n);
 
 
</script>
Producción: 

-1 10 -1 10 -1 20

 

Complejidad de tiempo: O(n Log n)

Espacio Auxiliar: O(n) 
 

Publicación traducida automáticamente

Artículo escrito por kartik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *