Die Daily Challenge von Leetcode wurde in den letzten Monaten durchgeführt Dies ist das erste Mal, dass ich eine Antworterklärung zu Qiita veröffentlicht habe. Wenn Sie es nützlich finden, mögen Sie es bitte und hinterlassen Sie einen Kommentar.
Das heutige Problem ist:
H-Index II
Given an array of citations sorted in ascending order (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
Example: Input: citations = [0,1,3,5,6] Output: 3 Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, her h-index is 3.
Ich habe es vorerst auf Englisch kopiert, aber Sie können die Bedeutung verstehen.
Zuerst möchte ich den H-Index finden Was ist H-Index? Wenn es ein Array gibt und die Anzahl der Zahlen über X genau X ist, heißt der H-Index dieses Arrays X.
Wenn Sie den Zweck kennen, wie sollten Sie ihn als nächstes lösen? Ich habe einen Hinweis. Haben Sie bemerkt, dass das Array bereits sortiert ist? Denken Sie zunächst an die "Dichotomie" für das sortierte Array.
Ich habe es hier auch nicht eingefügt, aber es steht in Follow Up:
•Could you solve it in logarithmic time complexity?
"Können Sie mit logarithmischer Zeitkomplexität lösen?" Mit anderen Worten, verwenden Sie "Dichotomie". ..
Um ehrlich zu sein, ist "Dichotomie" ein schwieriges Thema, aber es gibt Vorlagen:
int n = citations.length;
//Platzieren Sie zuerst 2 Zeiger links und rechts
int left = 0;
int right = n - 1;
while(left <= right) {
int mid = left + (right - left) / 2;//Holen Sie sich den Mittelpunkt
if(n - mid == citations[mid]) {//Wenn Sie es finden, ist es vorbei
return n - mid;
} else if(n - mid > citations[mid]) {//Wenn es kleiner als das Ziel ist, drücken Sie von links
left = mid + 1;
} else {//Wenn es größer als das Ziel ist, drücken Sie von rechts
right = mid - 1;
}
}
return n - left;
Die Halbierungssuche ist wie folgt, daher sollten Sie sich daran erinnern. Es ist die IF-Bedingung, die sich jedes Mal je nach Problem geändert hat.
Ob diese Bedingung ** X ** erfüllt und die Anzahl der Zahlen ** X und höher ** Was ist ** die Anzahl der Zahlen über X **? Da es sortiert ist, sind alle Zahlen auf der rechten Seite von X größer als X, und die Zahl ist die Anzahl der Elemente auf der rechten Seite einschließlich X, die sogenannte Gesamtzahl n - ** Index von X ** Die Bedingung sollte also als "n --mid == citations [mid])" geschrieben werden
Das Letzte, in dem Sie sich verlieren könnten, ist die Frage, ob Sie hier Gleiches hinzufügen sollen oder nicht.
Einfach ausgedrückt hängt die Antwort von etwas anderem als einem Array ab. In diesem Fall wäre der H-Index 0, wenn alle 0 wären. Aber n --left erreicht nicht 0! Da es das Array überschreitet, tritt ein Fehler auf, wenn Sie keine Gleichheit hinzufügen.
Das ist alles für die Antwort und Erklärung. Ich habe es zum ersten Mal gemacht. Wenn Sie Fragen oder Fehler haben, können Sie sich gerne an mich wenden!