Suche-Algorithmus h-Index schnell

Question

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

Diese Wikiseite ist eine Definition von h-Index

grundsätzlich zu berechnen, wenn ich einen Arrays haben bin [0 3 4 7 8 9 10], Mein h-Index wäre 4, da ich 4 Zahlen größer als 4 hätte. Mein h-Index wäre 5 gewesen, wenn ich 5 Zahlen größer als 5 hätte, und usw. Bei einem Array von ganzen Zahlen größer oder gleich 0, Wie kann der h-index effizient berechnet werden?

edit: das Array nicht notwendigerweise sortiert

Answer 1

Hier ist meine Erkenntnis O (N) mit Einreichungs, ist dies einfach und blitzschnelle:

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

Dies ist eine Lösung, die ich denken konnte. nicht sicher, ob es das Beste ist.

Sortieren Sie das Array in aufsteigender Reihenfolge. Komplexität nlog (n)

Iterieren durch die Anordnung aus dem Index 0 bis n. Komplexität der n

und für jede Iteration wird suppose Index i

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

z.B.

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

Answer 3

Dies könnte in O (n) Zeit durchgeführt werden.

1. Suchen Sie den Median des Arrays.
2. Wenn der Median> (n-1)/2 ist, dann kommt die Zahl vor dem Median. Finden Sie es iterativ
3. Wenn Median < (n-1)/2 dann die Zahl nach dem Median kommt. Finde es iterativ.
4. Wenn Median == (n-1)/2 ist, dann ist der Median der Lösung

Hier ungerade dass n Ich gehe davon aus. Ändern Sie den Algorithmus leicht für gerade n (ersetzen Sie (n + 1)/2 durch n/2, wenn der Rang des Medianwerts n/2 ist). Außerdem ist es schwierig, den tatsächlichen Median in O (n) -Zeit zu finden. Verwenden Sie stattdessen einen guten Pivot (wie in Quicksort).

Komplexität: n + n/2 + n/4 ... = O (n)

Answer 4

Ich war nicht glücklich mit meiner vorherigen Implementierung, also ersetzte ich es durch eine schnellere Lösung in Java geschrieben.

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; 
}