Encuentre el valor más pequeño más cercano para cada elemento en la array

Dada una array de enteros, encuentre el elemento más pequeño más cercano para cada elemento. Si no hay un elemento más pequeño, imprima -1

Ejemplos: 

Entrada: arr[] = {10, 5, 11, 6, 20, 12} 
Salida: 6, -1, 10, 5, 12, 11 

Entrada: arr[] = {10, 5, 11, 10, 20, 12} 
Salida: 5 -1 10 5 12 11 
  

Una solución simple es ejecutar dos bucles anidados. Elegimos un elemento externo uno por uno. Para cada elemento seleccionado, recorremos la array restante y encontramos el elemento más pequeño más cercano. La complejidad temporal de esta solución es O(n*n)

Una mejor solución es utilizar la clasificación. Ordenamos todos los elementos, luego, para cada elemento, avanzamos hacia la izquierda hasta que encontramos un elemento más pequeño (Tenga en cuenta que puede haber múltiples ocurrencias de un elemento).

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 más pequeñas de inserción y más cercanas en tiempo O (Log n).

// C++ program to find closest smaller value for
// every array element
#include <bits/stdc++.h>
using namespace std;
 
void closestSmaller(int arr[], int n)
{
    // Insert all array elements into a TreeSet
    set<int> ts;
    for (int i = 0; i < n; i++)
        ts.insert(arr[i]);
 
    // Find largest smaller element for every
    // array element
    for (int i = 0; i < n; i++)
    {
        auto smaller = ts.lower_bound(arr[i]);
        if (smaller == ts.begin())
            cout << -1 << " ";
        else
            cout << *(--smaller) << " ";
    }
}
 
// Driver Code
int main()
{
    int arr[] = {10, 5, 11, 6, 20, 12};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    closestSmaller(arr, n);
 
    return 0;
}
 
// This code is contributed by
// sanjeev2552

// Java program to find closest smaller value for
// every array element
import java.util.*;
 
class TreeSetDemo {
    public static void closestSmaller(int[] arr)
    {
        // Insert all array elements into a TreeSet
        TreeSet<Integer> ts = new TreeSet<Integer>();
        for (int i = 0; i < arr.length; i++)
            ts.add(arr[i]);
 
        // Find largest smaller element for every
        // array element
        for (int i = 0; i < arr.length; i++) {
            Integer smaller = ts.lower(arr[i]);
            if (smaller == null)
                System.out.print(-1 + " ");
            else
                System.out.print(smaller + " ");
        }
    }
 
    public static void main(String[] args)
    {
        int[] arr = { 10, 5, 11, 6, 20, 12 };
        closestSmaller(arr);
    }
}

# Python3 program to find closest smaller value
# for every array element
import bisect
 
def closestSmaller(arr, n):
     
    # Insert all array elements into a TreeSet
    ts = set()
     
    for i in range(n):
        ts.add(arr[i])
 
    # Find largest smaller element for every
    # array element
    for i in range(n):
        smaller = bisect.bisect_left(list(ts), arr[i])
         
        if (smaller == 0):
            print(-1, end = " ")
        else:
            print((list(ts)[smaller - 1]), end = " ")
            smaller -= 1
 
# Driver Code
arr = [ 10, 5, 11, 6, 20, 12 ]
n = len(arr)
 
closestSmaller(arr, n)
 
# This code is contributed by rohitsingh07052

// C# program to find closest smaller value for
// every array element
using System;
using System.Linq;
using System.Collections.Generic;
 
public class TreeSetDemo {
  public static void closestSmaller(int[] arr)
  {
    // Insert all array elements into a TreeSet
    SortedSet<int> ts = new SortedSet<int>();
    for (int i = 0; i < arr.Length; i++)
      ts.Add(arr[i]);
 
    // Find largest smaller element for every
    // array element
    for (int i = 0; i < arr.Length; i++) {
      int smaller = lower_bound(ts, arr[i]);
 
      if (smaller == 0)
        Console.Write(-1 + " ");
      else
        Console.Write(smaller + " ");
    }
  }
  public static int lower_bound(SortedSet<int> s, int val)
  {
    List<int> temp = new List<int>();
    temp.AddRange(s);
    temp.Sort();
    temp.Reverse();
 
    if (temp.IndexOf(val) + 1 == temp.Count)
      return -1;
    return temp[temp.IndexOf(val) + 1];
  }
 
  public static void Main(String[] args)
  {
    int[] arr = { 10, 5, 11, 6, 20, 12 };
    closestSmaller(arr);
  }
}
 
// This code is contributed by Rajput-Ji

<script>
// javascript program to find closest smaller value for
// every array elementclass TreeSetDemo {
    function closestSmaller(arr)
    {
     
        // Insert all array elements into a TreeSet
        var ts = new Set();
        for (i = 0; i < arr.length; i++)
            ts.add(arr[i]);
 
        // Find largest smaller element for every
        // array element
        for (i = 0; i < arr.length; i++) {
            var smaller = upper_bound(ts, arr[i]);
            if (smaller == null)
                document.write(-1 + " ");
            else
                document.write(smaller + " ");
        }
    }
    function upper_bound(s, val)
    {
        let temp = [...s];
        temp.sort((a, b) => b - a);
        return temp[temp.indexOf(val) + 1];
    }
  
        var arr = [ 10, 5, 11, 6, 20, 12 ];
        closestSmaller(arr);
         
// This code is contributed by Rajput-Ji
</script>

6 -1 10 5 12 11

Complejidad de tiempo: O (n Log n)