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)