alla ricerca di algoritmo per calcolare h-index veloce

Question

http://en.wikipedia.org/wiki/H-index

questa pagina Wiki è una definizione di h-index

in fondo se dovessi avere una serie di [0 3 4 7 8 9 10], il mio h-index sarebbe 4 dato che ho 4 numeri più grandi di 4. Il mio h-index sarebbe stato 5 se avessi avuto 5 numeri più grandi di 5, e così via. Data una serie di numeri interi maggiori o uguali a 0, quali sono i modi per calcolare l'h-index in modo efficiente?

edit: la matrice non è necessariamente allineati

Answer 1

Ecco la mia realizzazione O (N) con presentazione, questo è semplice e velocissimo:

private static int GetHIndex(int[] m) 
{ 
    int[] s = new int[m.Length + 1]; 
    for (int i = 0; i < m.Length; i++) s[Math.Min(m.Length, m[i])]++; 

    int sum = 0; 
    for (int i = s.Length - 1; i >= 0; i--) 
    { 
     sum += s[i]; 
     if (sum >= i) 
      return i; 
    } 

    return 0; 
} 

Answer 2

Questa è una soluzione che ho potuto pensare. non sono sicuro se è il migliore

Ordinare la matrice in ordine crescente. complessità nlog (n)

scorrere la matrice dall'indice 0 a n. complessità n

e per ogni iterazione, indice supponiamo è i

if (arr[i] == (arr.length - (i+1)) 
    return arr[i] 

esempio,

arr =[ 0 3 4 7 8 9 10 ] 
arr[2] = 4 
i = 2 
arr.length = 7 
4 = (7- (2+1)) 

Answer 3

Questo potrebbe essere fatto in O (n).

1. Trova la mediana dell'array.
2. se mediana> (n-1)/2 quindi il numero arriva prima della mediana. Trova iterativamente
3. Se mediana < (n-1)/2, il numero viene dopo la mediana. Trovalo iterativamente.
4. Se == mediana (n-1)/2, allora la mediana è la soluzione

Qui io parto dal presupposto che n è dispari. Cambia leggermente l'algoritmo per anche n (sostituisci (n + 1)/2 con n/2 supponendo che il rango di mediana sia n/2). Inoltre, trovare la mediana effettiva nel tempo O (n) è complicata. Utilizzare invece un buon pivot (come in quicksort).

Complessità: n + n/2 + n/4 ... = O (n)

Answer 4

Non ero soddisfatto della mia precedente implementazione, quindi l'ho sostituito con una soluzione più veloce scritta in Java.

public int hIndex(int[] citations) { 
    if(citations == null || citations.length == 0) 
    { 
     return 0; 
    } 

    Arrays.sort(citations); 

    int hIndex = 0; 

    for(int i=0;i<citations.length;i++) 
    { 
     int hNew; 

     if(citations[i]<citations.length-i) 
     { 
      hNew = citations[i]; 

      if(hNew>hIndex) 
      { 
       hIndex = hNew; 
      } 
     } 
     else if(citations[i]>=citations.length-i) 
     { 
      hNew = citations.length-i; 

      if(hNew>hIndex) 
      { 
       hIndex = hNew; 
      } 

      break; 
     } 
    } 

    return hIndex; 
}