Dada una array de citas [] que consta de N números enteros en orden no creciente, que representan citas, la tarea es encontrar el índice H.
El índice H generalmente se asigna al investigador y denota las contribuciones realizadas en términos de número de artículos y citas. El índice H (H) es el valor más grande tal que el investigador tiene al menos H artículos citados al menos H veces.
Ejemplos:
Entrada: citas[] = {5, 3, 3, 0, 0}
Salida: 3
Explicación:
Hay al menos 3 artículos (5, 3, 3) con al menos 3 citas
Entrada: citas[] = {5, 4, 2 , 1, 1}
Salida: 2
Explicación:
Hay al menos 2 artículos (5, 4, 2) con al menos 2 citas.
Enfoque ingenuo: una solución simple es iterar a través de los documentos de izquierda a derecha e incrementar el índice H mientras que las citas i son mayores o iguales que el índice.
Complejidad de tiempo: O(N)
Enfoque eficiente: la idea es utilizar la búsqueda binaria para optimizar el enfoque anterior. El índice H puede estar en el rango de 0 a N. Para verificar si un valor dado es posible o no, verifique si las citas [valor] son mayores o iguales que el valor .
- Inicialice el rango de búsqueda para la búsqueda binaria como 0 a N .
- Encuentre el elemento medio del rango.
- Compruebe si el elemento central de la cita es menor que el índice. Si es así, actualice el rango izquierdo al elemento central.
- De lo contrario, verifique si el elemento central de la cita es mayor que el índice. Si es así, actualice el rango correcto al elemento central.
- De lo contrario, el índice dado es el índice H de las citas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the H-index
int hIndex(vector<int> citations,
int n)
{
int hindex = 0;
// Set the range for binary search
int low = 0, high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
// Check if current citations is
// possible
if (citations[mid] >= (mid + 1)) {
// Check to the right of mid
low = mid + 1;
// Update h-index
hindex = mid + 1;
}
else {
// Since current value is not
// possible, check to the left
// of mid
high = mid - 1;
}
}
// Print the h-index
cout << hindex << endl;
return hindex;
}
// Driver Code
int main()
{
// citations
int n = 5;
vector<int> citations = { 5, 3, 3, 2, 2 };
hIndex(citations, n);
}
Java
// Java implementation of the
// above approach
import java.io.*;
class GFG{
// Function to find the H-index
static int hIndex(int[] citations, int n)
{
int hindex = 0;
// Set the range for binary search
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
// Check if current citations is
// possible
if (citations[mid] >= (mid + 1))
{
// Check to the right of mid
low = mid + 1;
// Update h-index
hindex = mid + 1;
}
else
{
// Since current value is not
// possible, check to the left
// of mid
high = mid - 1;
}
}
// Print the h-index
System.out.println(hindex);
return hindex;
}
// Driver Code
public static void main (String[] args)
{
// citations
int n = 5;
int[] citations = { 5, 3, 3, 2, 2 };
hIndex(citations, n);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 implementation of the # above approach # Function to find the H-index def hIndex(citations, n): hindex = 0 # Set the range for binary search low = 0 high = n - 1 while (low <= high): mid = (low + high) // 2 # Check if current citations is # possible if (citations[mid] >= (mid + 1)): # Check to the right of mid low = mid + 1 # Update h-index hindex = mid + 1 else: # Since current value is not # possible, check to the left # of mid high = mid - 1 # Print the h-index print(hindex) return hindex # Driver Code # citations n = 5 citations = [ 5, 3, 3, 2, 2 ] # Function Call hIndex(citations, n) # This code is contributed by Shivam Singh
C#
// C# implementation of the
// above approach
using System;
class GFG{
// Function to find the H-index
static int hIndex(int[] citations, int n)
{
int hindex = 0;
// Set the range for binary search
int low = 0, high = n - 1;
while (low <= high)
{
int mid = (low + high) / 2;
// Check if current citations is
// possible
if (citations[mid] >= (mid + 1))
{
// Check to the right of mid
low = mid + 1;
// Update h-index
hindex = mid + 1;
}
else
{
// Since current value is not
// possible, check to the left
// of mid
high = mid - 1;
}
}
// Print the h-index
Console.WriteLine(hindex);
return hindex;
}
// Driver Code
public static void Main ()
{
// citations
int n = 5;
int[] citations = { 5, 3, 3, 2, 2 };
hIndex(citations, n);
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the H-index
function hIndex(citations, n)
{
let hindex = 0;
// Set the range for binary search
let low = 0, high = n - 1;
while (low <= high)
{
let mid = (low + high) / 2;
// Check if current citations is
// possible
if (citations[mid] >= (mid + 1))
{
// Check to the right of mid
low = mid + 1;
// Update h-index
hindex = mid + 1;
}
else
{
// Since current value is not
// possible, check to the left
// of mid
high = mid - 1;
}
}
// Print the h-index
document.write(hindex);
return hindex;
}
// Driver code
// citations
let n = 5;
let citations = [ 5, 3, 3, 2, 2 ];
hIndex(citations, n)
// This code is contributed by target_2.
</script>
3
Complejidad temporal: O(logN)
Espacio auxiliar: O(1)