Dada una array de enteros, encuentre el elemento mayor o igual más cercano para cada elemento. Si todos los elementos son más pequeños para un elemento, imprima -1
Ejemplos:
Entrada: arr[] = {10, 5, 11, 10, 20, 12}
Salida: 10 10 12 10 -1 20
Tenga en cuenta que hay varias apariciones de 10, por lo que el techo de 10 es 10 en sí mismo.
Entrada: arr[] = {6, 11, 7, 8, 20, 12}
Salida: 7 12 8 11 -1 20
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 mayor más cercano. La complejidad temporal de esta solución es O(n*n)
Otro enfoque usando Hashing:
La solución es almacenar la respuesta para cada elemento en un mapa (digamos res). Y esto se puede hacer usando un segundo mapa (digamos m) que almacenará la frecuencia de los elementos y los clasificará automáticamente según las claves. Luego recorra el mapa m y encuentre la respuesta a cada clave y almacene la respuesta en el mapa res[clave].
Complejidad de tiempo: O(n)
Complejidad espacial:O(n)
C++
// C++ implementation to find the closest smaller or same
// element for every element.
#include <bits/stdc++.h>
using namespace std;
map<int, int> m; // initialise two maps
map<int, int> res;
void printPrevGreater(int arr[], int n)
{
for (int i = 0; i < n; i++) {
m[arr[i]]++; // Add elements to map to store count
}
int c = 0;
int prev;
int f = 0;
for (auto i = m.begin(); i != m.end(); i++) {
if (f == 1) {
res[prev] = i->first;// check if previous element have
// no similar element ,store next
// element occurring in map in
// res[previous_element]
f = 0;
c++;
}
if (i->second == 1) { // if current element count is
// 1 then its greater value
// will be map's next element
f = 1;
prev = i->first;
}
else if (i->second
> 1) { // if current element count is
// greater than 1, it means there are
// similar elements
res[i->first] = i->first;
c++;
f = 0;
}
}
if (c < n) {
res[prev] = -1; // checks whether the value for the last
// element in map m is stores in res or
// not. if not set value to -1 as no other
// greater element is there.
}
for (int i = 0; i < n; i++) { // print the elements
cout << res[arr[i]] << " ";
}
}
int main()
{
int arr[] = { 6, 11, 7, 8, 20, 12 };
int n = sizeof(arr) / sizeof(arr[0]);
printPrevGreater(arr, n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG
{
// Java implementation to find the closest smaller or same
// element for every element.
static Map<Integer,Integer> m = new TreeMap<>(); // initialise two maps
static Map<Integer,Integer> res = new TreeMap<>();
static void printPrevGreater(int arr[], int n)
{
for (int i = 0; i < n; i++) {
if(m.containsKey(arr[i])){
m.put(arr[i], m.get(arr[i])+1);
}
else m.put(arr[i],1); // Add elements to map to store count
}
int c = 0;
int prev = 0;
int f = 0;
for (Map.Entry<Integer, Integer>entry : m.entrySet()) {
if (f == 1) {
res.put(prev,entry.getKey());// check if previous element have
// no similar element ,store next
// element occurring in map in
// res[previous_element]
f = 0;
c++;
}
if (entry.getValue() == 1) { // if current element count is
// 1 then its greater value
// will be map's next element
f = 1;
prev = entry.getKey();
}
else if (entry.getValue() > 1) { // if current element count is
// greater than 1, it means there are
// similar elements
res.put(entry.getKey() , entry.getKey());
c++;
f = 0;
}
}
if (c < n) {
res.put(prev , -1); // checks whether the value for the last
// element in map m is stores in res or
// not. if not set value to -1 as no other
// greater element is there.
}
for (int i = 0; i < n; i++) { // print the elements
System.out.printf("%d ",res.get(arr[i]));
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 6, 11, 7, 8, 20, 12 };
int n = arr.length;
printPrevGreater(arr, n);
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 implementation to find the closest smaller or
# same element for every element.
m = {}; # initialise two maps
res = {};
def printPrevGreater(arr, n):
for i in range(n):
if arr[i] not in m:
m[arr[i]] = 0
m[arr[i]] += 1 # Add elements to map to store count
c = 0;
f = 0;
for i in sorted(m) :
if (f == 1) :
# check if previous element have
# no similar element ,store next
# element occurring in map in
# res[previous_element]
res[prev] = int(i)
f = 0;
c += 1;
if (m[i] == 1):
# if current element count is
# 1 then its greater value
# will be map's next element
f = 1;
prev = int(i);
elif (m[i] > 1):
# if current element count is
# greater than 1, it means
# there are similar elements
res[int(i)] = int(i);
c += 1
f = 0;
if (c < n):
res[prev] = -1;
# checks whether the value for the last
# element in map m is stores in res or
# not. if not set value to -1 as no other
# greater element is there.
for i in range(n): # print the elements
print(res[arr[i]], end = " ");
# Driver Code
arr = [ 6, 11, 7, 8, 20, 12 ];
n = len(arr);
printPrevGreater(arr, n);
# This code is contributed by phasing17
C#
// C# implementation to find the closest smaller or same
// element for every element.
using System;
using System.Collections.Generic;
class GFG
{
// initialise two maps
static SortedDictionary<int, int> m =
new SortedDictionary<int, int>();
static SortedDictionary<int, int> res =
new SortedDictionary<int, int>();
static void printPrevGreater(int[] arr, int n)
{
for (int i = 0; i < n; i++) {
if(m.ContainsKey(arr[i])){
m[arr[i]] += 1;
}
else m[arr[i]] = 1; // Add elements to map to store count
}
int c = 0;
int prev = 0;
int f = 0;
foreach (var entry in m) {
if (f == 1) {
res[prev] = entry.Key;// check if previous element have
// no similar element ,store next
// element occurring in map in
// res[previous_element]
f = 0;
c++;
}
if (entry.Value == 1) { // if current element count is
// 1 then its greater value
// will be map's next element
f = 1;
prev = entry.Key;
}
else if (entry.Value > 1) { // if current element count is
// greater than 1, it means there are
// similar elements
res[entry.Key] = entry.Key;
c++;
f = 0;
}
}
if (c < n) {
res[prev] = -1; // checks whether the value for the last
// element in map m is stores in res or
// not. if not set value to -1 as no other
// greater element is there.
}
for (int i = 0; i < n; i++) { // print the elements
Console.Write(res[arr[i]] + " ");
}
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 6, 11, 7, 8, 20, 12 };
int n = arr.Length;
printPrevGreater(arr, n);
}
}
// This code is contributed by phasing17
Javascript
// JavaScript implementation to find the closest smaller or
// same element for every element.
let m = {}; // initialise two maps
let res = {};
function printPrevGreater(arr, n)
{
for (var i = 0; i < n; i++) {
if (!m.hasOwnProperty(arr[i]))
m[arr[i]] = 0;
m[arr[i]]++; // Add elements to map to store count
}
let c = 0;
let prev;
let f = 0;
for (const i in m) {
if (f == 1) {
res[prev] = parseInt(
i); // check if previous element have
// no similar element ,store next
// element occurring in map in
// res[previous_element]
f = 0;
c++;
}
if (m[i] == 1) { // if current element count is
// 1 then its greater value
// will be map's next element
f = 1;
prev = parseInt(i);
}
else if (m[i] > 1) { // if current element count is
// greater than 1, it means
// there are similar elements
res[parseInt(i)] = parseInt(i);
c++;
f = 0;
}
}
if (c < n) {
res[prev]
= -1; // checks whether the value for the last
// element in map m is stores in res or
// not. if not set value to -1 as no other
// greater element is there.
}
for (var i = 0; i < n; i++) { // print the elements
process.stdout.write(res[arr[i]] + " ");
}
}
// Driver Code
let arr = [ 6, 11, 7, 8, 20, 12 ];
let n = arr.length;
printPrevGreater(arr, n);
// This code is contributed by phasing17
Una mejor solución es ordenar la array y crear una copia ordenada, luego realizar una búsqueda binaria de piso. Recorremos la array, para cada elemento buscamos el primer elemento mayor. En C++ , upper_bound() sirve para este propósito.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of efficient algorithm to find
// floor of every element
#include <bits/stdc++.h>
using namespace std;
// Prints greater elements on left side of every element
void printPrevGreater(int arr[], int n)
{
if (n == 1) {
cout << "-1";
return;
}
// Create a sorted copy of arr[]
vector<int> v(arr, arr + n);
sort(v.begin(), v.end());
// Traverse through arr[] and do binary search for
// every element.
for (int i = 0; i < n; i++) {
// Find the first element that is greater than
// the given element
auto it = upper_bound(v.begin(), v.end(), arr[i]);
// Since arr[i] also exists in array, *(it-1)
// will be same as arr[i]. Let us check *(it-2)
// is also same as arr[i]. If true, then arr[i]
// exists twice in array, so ceiling is same
// same as arr[i]
if ((it - 1) != v.begin() && *(it - 2) == arr[i]) {
// If next element is also same, then there
// are multiple occurrences, so print it
cout << arr[i] << " ";
}
else if (it != v.end())
cout << *it << " ";
else
cout << -1 << " ";
}
}
/* 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
// floor of every element
import java.util.Arrays;
class GFG
{
// Prints greater elements on left side of every element
static void printPrevGreater(int arr[], int n)
{
if (n == 1)
{
System.out.println("-1");
return;
}
// Create a sorted copy of arr[]
int v[] = Arrays.copyOf(arr, arr.length);
Arrays.sort(v);
// Traverse through arr[] and do binary search for
// every element.
for (int i = 0; i < n; i++)
{
// Find the first element that is greater than
// the given element
int it = Arrays.binarySearch(v,arr[i]);
it++;
// Since arr[i] also exists in array, *(it-1)
// will be same as arr[i]. Let us check *(it-2)
// is also same as arr[i]. If true, then arr[i]
// exists twice in array, so ceiling is same
// same as arr[i]
if ((it - 1) != 0 && v[it - 2] == arr[i])
{
// If next element is also same, then there
// are multiple occurrences, so print it
System.out.print(arr[i] + " ");
}
else if (it != v.length)
System.out.print(v[it] + " ");
else
System.out.print(-1 + " ");
}
}
// 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
// Rajnis09
Python3
# Python implementation of efficient algorithm
# to find floor of every element
import bisect
# Prints greater elements on left side of every element
def printPrevGreater(arr, n):
if n == 1:
print("-1")
return
# Create a sorted copy of arr[]
v = list(arr)
v.sort()
# Traverse through arr[] and do binary search for
# every element
for i in range(n):
# Find the location of first element that
# is greater than the given element
it = bisect.bisect_right(v, arr[i])
# Since arr[i] also exists in array, v[it-1]
# will be same as arr[i]. Let us check v[it-2]
# is also same as arr[i]. If true, then arr[i]
# exists twice in array, so ceiling is same
# same as arr[i]
if (it-1) != 0 and v[it-2] == arr[i]:
# If next element is also same, then there
# are multiple occurrences, so print it
print(arr[i], end=" ")
elif it <= n-1:
print(v[it], end=" ")
else:
print(-1, end=" ")
# Driver code
if __name__ == "__main__":
arr = [10, 5, 11, 10, 20, 12]
n = len(arr)
printPrevGreater(arr, n)
# This code is contributed by
# sanjeev2552
C#
// C# implementation of efficient algorithm
// to find floor of every element
using System;
class GFG
{
// Prints greater elements on left side
// of every element
static void printPrevGreater(int []arr, int n)
{
if (n == 1)
{
Console.Write("-1");
return;
}
// Create a sorted copy of arr[]
int []v = new int[arr.GetLength(0)];
Array.Copy(arr, v, arr.GetLength(0));
Array.Sort(v);
// Traverse through arr[] and
// do binary search for every element.
for (int i = 0; i < n; i++)
{
// Find the first element that is
// greater than the given element
int it = Array.BinarySearch(v, arr[i]);
it++;
// Since arr[i] also exists in array, *(it-1)
// will be same as arr[i]. Let us check *(it-2)
// is also same as arr[i]. If true, then arr[i]
// exists twice in array, so ceiling is same
// same as arr[i]
if ((it - 1) != 0 && v[it - 2] == arr[i])
{
// If next element is also same, then there
// are multiple occurrences, so print it
Console.Write(arr[i] + " ");
}
else if (it != v.Length)
Console.Write(v[it] + " ");
else
Console.Write(-1 + " ");
}
}
// 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 29AjayKumar
Producción:
10 10 12 10 -1 20
Complejidad de Tiempo : O(n Log n)
Espacio Auxiliar : O(n)