Dada una array arr[] que consta de N enteros no negativos, la tarea es encontrar un entero K para cada índice tal que al menos K enteros en la array hasta ese índice sean mayores o iguales a K.
Nota: considere la indexación basada en 1
Ejemplos:
Entrada: arr[] = {3, 0, 6, 1, 5}
Salida: K = {1, 1, 2, 2, 3}
Explicación:
En el índice 1, hay 1 número mayor o igual que 1 en el array, es decir, 3. Entonces, el valor K para los elementos hasta el índice 1 es 1.
En el índice 2, hay 1 número mayor o igual que 1 en la array, es decir, 3. Entonces, el valor K para los elementos hasta el índice 2 es 1.
En el índice 3, hay 2 números mayores o iguales a 2 en la array, es decir, 3 y 6. Por lo tanto, el valor de K para los elementos hasta el índice 3 es 2. En el índice 4, hay 2 números mayores o iguales a
2 en la array, es decir, 3 y 6. Entonces, el valor K para los elementos hasta el índice 4 es 2.
En el índice 5, hay 3 números mayores o iguales a 3 en la array, es decir, 3, 6 y 5. Por lo tanto, el valor de K para los elementos hasta el índice 5 es 3.Entrada: arr[] = {9, 10, 7, 5, 0, 10, 2, 0}
Salida: K = {1, 2, 3, 4, 4, 5, 5, 5}
Enfoque ingenuo:
el enfoque más simple es encontrar el valor de K para todos los elementos de la array en el rango [0, i] , donde i es el índice de la array arr[] , utilizando el enfoque eficiente utilizado en el enlace del artículo se da aquí .
Complejidad de tiempo: O(N 2 )
Complejidad de espacio: O(N)
Enfoque eficiente:
la idea es usar Multiset (árbol rojo-negro) . Multiset almacena los valores en un orden ordenado que ayuda a verificar si el valor mínimo actual en el multiset es mayor o igual a su tamaño. En caso afirmativo, entonces el valor del entero K será el tamaño del conjunto múltiple.
A continuación se detallan los pasos para la implementación:
- Atraviese la array desde el índice 0 hasta N-1.
- Para cada índice, inserte el elemento en el conjunto múltiple y verifique si el valor más pequeño en el conjunto múltiple es menor que el tamaño del conjunto múltiple.
- Si es verdadero, borre el elemento inicial e imprima el tamaño del conjunto múltiple.
- Si es falso, simplemente imprima el tamaño del conjunto múltiple.
- El tamaño del conjunto múltiple es el valor K requerido para cada índice i.
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 K-value
// for every index in the array
int print_h_index(int arr[], int N)
{
// Multiset to store the array
// in the form of red-black tree
multiset<int> ms;
// Iterating over the array
for (int i = 0; i < N; i++) {
// Inserting the current
// value in the multiset
ms.insert(arr[i]);
// Condition to check if
// the smallest value
// in the set is less than
// it's size
if (*ms.begin()
< ms.size()) {
// Erase the smallest
// value
ms.erase(ms.begin());
}
// h-index value will be
// the size of the multiset
cout << ms.size() << " ";
}
}
// Driver Code
int main()
{
// array
int arr[] = { 9, 10, 7, 5, 0,
10, 2, 0 };
// Size of the array
int N = sizeof(arr)
/ sizeof(arr[0]);
// function call
print_h_index(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the K-value
// for every index in the array
static void print_h_index(int arr[], int N)
{
// Multiset to store the array
// in the form of red-black tree
List<Integer> ms = new ArrayList<Integer>();
// Iterating over the array
for(int i = 0; i < N; i++)
{
// Inserting the current
// value in the multiset
ms.add(arr[i]);
// Condition to check if
// the smallest value
// in the set is less than
// it's size
int t = Collections.min(ms);
if (t < ms.size())
{
// Erase the smallest
// value
ms.remove(ms.indexOf(t));
}
// h-index value will be
// the size of the multiset
System.out.print(ms.size() + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Array
int arr[] = { 9, 10, 7, 5, 0,
10, 2, 0 };
// Size of the array
int N = arr.length;
// Function call
print_h_index(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach # Function to find the K-value # for every index in the array def print_h_index(arr, N): # Multiset to store the array # in the form of red-black tree ms = [] # Iterating over the array for i in range(N): # Inserting the current # value in the multiset ms.append(arr[i]) ms.sort() # Condition to check if # the smallest value # in the set is less than # it's size if (ms[0] < len(ms)): # Erase the smallest # value ms.pop(0) # h-index value will be # the size of the multiset print(len(ms), end = ' ') # Driver Code if __name__=='__main__': # Array arr = [ 9, 10, 7, 5, 0, 10, 2, 0 ] # Size of the array N = len(arr) # Function call print_h_index(arr, N) # This code is contributed by pratham76
C#
// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG{
// Function to find the K-value
// for every index in the array
static void print_h_index(int []arr, int N)
{
// Multiset to store the array
// in the form of red-black tree
ArrayList ms = new ArrayList();
// Iterating over the array
for(int i = 0; i < N; i++)
{
// Inserting the current
// value in the multiset
ms.Add(arr[i]);
// Condition to check if
// the smallest value
// in the set is less than
// it's size
int t = int.MaxValue;
foreach(int x in ms)
{
if(x < t)
{
t = x;
}
}
if (t < ms.Count)
{
// Erase the smallest
// value
ms.Remove(t);
}
// h-index value will be
// the size of the multiset
Console.Write(ms.Count + " ");
}
}
// Driver code
public static void Main(string[] args)
{
// Array
int []arr = { 9, 10, 7, 5, 0,
10, 2, 0 };
// Size of the array
int N = arr.Length;
// Function call
print_h_index(arr, N);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program for the above approach
// Function to find the K-value
// for every index in the array
function print_h_index(arr, N)
{
// Multiset to store the array
// in the form of red-black tree
var ms = [];
// Iterating over the array
for (var i = 0; i < N; i++) {
// Inserting the current
// value in the multiset
ms.push(arr[i]);
ms.sort((a,b)=> a-b)
// Condition to check if
// the smallest value
// in the set is less than
// it's size
if (ms[0]
< ms.length) {
// Erase the smallest
// value
ms.shift();
}
// h-index value will be
// the size of the multiset
document.write( ms.length + " ");
}
}
// Driver Code
// array
var arr = [9, 10, 7, 5, 0,
10, 2, 0 ];
// Size of the array
var N = arr.length;
// function call
print_h_index(arr, N);
</script>
1 2 3 4 4 5 5 5
Complejidad de tiempo: O(N * log(N))
Complejidad de espacio auxiliar: O(N)