Le défi quotidien de Leetcode a eu lieu ces derniers mois C'est la première fois que je poste une explication de réponse sur Qiita. Si vous le trouvez utile, veuillez l'aimer et laisser un commentaire.
Le problème d'aujourd'hui est:
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.
Je l'ai copié en anglais pour le moment, mais vous pouvez comprendre le sens.
Tout d'abord, je veux trouver le H-Index Qu'est-ce que l'indice H? S'il y a un tableau et que le nombre de nombres au-dessus de X est exactement X, l'indice H de ce tableau est appelé X.
Une fois que vous connaissez le but, comment devriez-vous le résoudre ensuite? J'ai un indice. Avez-vous remarqué que le tableau est déjà trié? Tout d'abord, pensez à la "dichotomie" pour le tableau trié.
De plus, je ne l'ai pas collé ici, mais il est dit dans Follow Up:
•Could you solve it in logarithmic time complexity?
"Pouvez-vous résoudre avec une complexité temporelle logarithmique?" En d'autres termes, utilisez "dichotomie". ..
Pour être honnête, la "dichotomie" est un sujet difficile, mais il existe des modèles:
int n = citations.length;
//Tout d'abord, placez 2 pointeurs à gauche et à droite
int left = 0;
int right = n - 1;
while(left <= right) {
int mid = left + (right - left) / 2;//Obtenez le point médian
if(n - mid == citations[mid]) {//Si tu le trouves, c'est fini
return n - mid;
} else if(n - mid > citations[mid]) {//S'il est plus petit que la cible, appuyez à partir de la gauche
left = mid + 1;
} else {//S'il est plus grand que la cible, appuyez à partir de la droite
right = mid - 1;
}
}
return n - left;
La recherche de bissection est comme ça, vous devez donc vous en souvenir. C'est la condition IF qui a changé en fonction du problème à chaque fois.
Si cette condition satisfait ** X ** et le nombre de nombres ** X et plus **
Quel est ** le nombre de nombres au-dessus de X **? Puisqu'il est trié, tous les nombres sur le côté droit de X sont plus grands que X, et le nombre est le nombre d'éléments sur la droite incluant X, soi-disant nombre total n - ** Index de X **
La condition doit donc être écrite comme n --mid == citations [mid])
La dernière chose dans laquelle vous pourriez vous perdre est la question de savoir s'il faut ajouter des égaux ici ou non.
En termes simples, la réponse dépend de quelque chose d'autre qu'un tableau.Dans ce cas, si tous étaient 0, alors H-Index serait 0. Mais n --left n'atteint pas 0! Puisqu'il dépasse le tableau, une erreur se produit si vous n'ajoutez pas d'égalité.
C'est tout pour la réponse et l'explication. Je l'ai fait pour la première fois, donc si vous avez des questions ou des erreurs, n'hésitez pas à me contacter!