Hirsch-Index berechnen

[BlackParrot]

Hallo liebe Community!
Ich habe ein Programm, bei dem ich nicht weiter komme. Und zwar möchte ich ein Programm schreiben, das den Hirschindex berechnet. Das ist die größte natürliche Zahl m, für die gilt, dass ein Wissenschaftler m Veröffentlichungen hat, die mindestens m-mal zitiert wurden. Die Eingabe soll ein int-Array sein. Diese sehen dann z.b. so aus: [1, 3, 2, 2, 4, 1, 1]. Die Zahlen stellen die Nummer der einzelnen Veröffentlichungen dar und die Anzahl der gleichen Nummer sagt, wie oft diese Veröffentlichung zitiert wurde. Hier ist also der Hirsch-Index 2, da die Veröffentlichungen 1 und 2 mindestens zweimal zitiert wurden. Die Anzahl der Zitierungen, also die Arraylänge, ist n.
Hat jemand eine Idee, wie dies in Java programmiert werden könnte?
Ich wäre euch sehr dankbar!

 

[Nuiton]

Direkt mal gegooglet.

public int hIndex(int[] citations) {
    Arrays.sort(citations);

    int result = 0;  
    for(int i=0; i<citations.length; i++){
        int smaller = Math.min(citations[i], citations.length-i);
        result = Math.max(result, smaller);
    }

    return result;
}

 

[BlackParrot]

Hallo Nuiton,
ja das habe ich auch schon gefunden. Das Problem ist nur, dass dieser Algorithmus mit einer Eingabe arbeitet, die folgende Form hat: Sie ist ein Array, in dessen Felder die Anzahl der Zitierungen pro Veröffentlichung des Wissenschaftlers gespeichert ist. Mein Eingabe-Array soll allerdings andere Daten enthalten: Die Felder sollen der Reihe nach sagen, welche Veröffentlichung zitiert wurde: [4, 3, 3, 1, 2, 1] sagt zB, dass zuerst die vierte, dann zweimal die dritte, dann die erste, dann die zweite und danach noch einmal die erste Veröffentlichung zitiert wurde. Also kann der obige Algorithmus mit dieser Eingabeform nicht den richtigen Hirsch-Index berechnen.
Hat jemand eine Idee wie ich das hinbekomme?

 

[Nuiton]

Eh, no comprende. Was willst du denn jetzt berechnen? Du meintest im Eingangspost, du willst den Hirsch-Index berechnen - der ist oben. Wenn du eine spezielle Ausgabe haben willst, dann musst du die Methode erweitern.

Nebenbei sind [4,3,3,1,2,1] und [1,3,2,2,4,1,1] auch ganz andere Arrays, die eine ganz andere Anzahl an Zahlen beinhalten.

 

[BlackParrot]

Hallo, dass die zwei von mir genannten Array unterschiedlich sind ist mir schon klar. Es sollten auch nur Beispiele sein. Was ich haben will ist als Ausgabe der Hirschindex. Allerdings soll die Form der Eingabe anders aussehen. Die Eingabe soll nicht in den einzelnen Feldern die Anzahl er einzelnen Zitierungen pro Werk enthalten, sondern das jeweilige Werk (Werk-Nr. 1, 2, 3, vier usw.) benennen, das zitiert wurde.

 

[mrBrown]

Dann überführ die eine Form in die andere.
Einfach über das eine iterieren, und jeweils den Wert als Index des anderen nutzen und dort incrementieren

 

[BlackParrot]

Hallo mrBrown,
leider sind meine Java-Fähigkeiten noch nicht ganz so ausgereift. Ich verstehe deine Idee, weiß aber nicht, wie ich sie umsetzten kann:
- ich erstelle zunächst ein zweites Array (aber welche Länge?)
- dann verwende ich eine for-Schleife von 0 bis Länge des ersten Arrays - 1
- dann teste ich, ob der Wert von A kleiner als A[i+1] ist
- falls ja, dann ist der Wert von A der Index von Array B, dessen Inhalt ich um eins erhöhe

Habe ich das richtig verstanden? Und wie könnte ich das in Java schreiben?
Wäre super wenn ihr mir helfen könntet.

 

[mrBrown]

- ich erstelle zunächst ein zweites Array (aber welche Länge?)

Länge = Anzahl der Werke, also der höchste Wert aus dem anderem Array

- dann verwende ich eine for-Schleife von 0 bis Länge des ersten Arrays - 1

Genau

- dann teste ich, ob der Wert von A kleiner als A[i+1] ist

Ist überflüssig, wenn du direkt die passende Länge benutzt

- falls ja, dann ist der Wert von A der Index von Array B, dessen Inhalt ich um eins erhöhe

Ja, dabei nur aufpassen mit 0-basiertem-Index

Habe ich das richtig verstanden? Und wie könnte ich das in Java schreiben?
Wäre super wenn ihr mir helfen könntet.

Versuchs doch mal selbst umzusetzen, wenn du dabei nicht weiterkommst kann man dir sicher besser helfen

 

[BlackParrot]

Vielen Dank mrBrown! Ich werde es gleich mal ausprobieren.

Aber eine andere Frage bezüglich dieser Aufgabe:
Könnte man das oben von mir benannte Problem evtl. mit einem Heap lösen? Hat dazu vielleicht jemand eine Idee?

 

[mrBrown]

Ja kann man, du entfernst einfach so lange das größte Element, bis die Anzahl der entfernten Elemente größer ist als das Element selbst. Der Index ist dann die Anzahl-1 (wenn ich grad keinen Dreher drin hab)

 

[BlackParrot]

Meinst du Folgendes?

- Aus der Eingabe (Int-Array bestehend aus der Nennung der jeweiligen Veröffentlichung, wenn sie zitiert wurde) wird zuerst ein MaxHeap gebaut
- Ich entferne die Wurzel des Heaps und baue aus dem Rest wieder einen MaxHeap (für jedes Entfernen erhöhe ich einen Zähler um 1)
-> dies wiederhole ich so lange, bis der Zähler größer als die Wurzel des Heaps ist
- der Hirsch-Index ist dann der Zähler minus 1

Habe ich das so richtig verstanden?
Vielen Dank, dass Du so viel Geduld mit mir hast...

 

[mrBrown]

Ja, dürfte so passen (unter uU ist das -1 unpassend, einfach mal testen)