H-Index (M)
題目
Given an array of citations (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 = [3,0,6,1,5]
Output: 3
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had
received 3, 0, 6, 1, 5 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.
Note: If there are several possible values for h, the maximum one is taken as the h-index.
題意
設一個研究者共有n篇論文，如果其中有h篇，這h篇中每一篇都被參考過至少h次，而剩余的n-h篇中每一篇被參考的次數都不超過h，則稱h為這個研究者的h指數，求一個研究者h指數的最大值，
思路
h的范圍很明顯是 0-n，所以只要從n往回找到第一個滿足的h，就是答案，因此可以這樣處理：先將陣列按升序排序，從頭遍歷陣列，對于每一個i，length - i即為從i到最后一個元素的長度len，如果citations[i] >= len，說明后面len個論文的參考次數都大于等于len，且前面所有i個論文的參考次數必不大于len (證明如下)，因此len就是要找的h指數，
證明：假設在i處找到了滿足的len，那么有 citations[i] > len (等于的情況無需證明)，如果 citations[i - 1] > len，一定有 citations[i - 1] >= len + 1 (因為是整數)，那么說明在i - 1處就應該已經找到了滿足的len值，但實際情況并不是，所以 citation[i - 1] <= len，證明前i個論文的參考次數一定都不超過len，滿足題目要求，
也可以不用排序：記citations.length為n，建一個長度為n + 1的輔助陣列aux，aux[i]表示參考次數等于i的論文篇數，aux[n]表示參考次數大于等于n的論文篇數，遍歷citations，如果citations[i] > n，則aux[n]++，否則aux[citations[i]]++，再從后向前遍歷aux陣列，統計當前和是否大于等于當前下標index，是的話說明index就是所要求的的h指數，
代碼實作
Java
排序
class Solution {
public int hIndex(int[] citations) {
Arrays.sort(citations);
for (int i = 0; i < citations.length; i++) {
if (citations[i] >= citations.length - i) {
return citations.length - i;
}
}
return 0;
}
}
不排序
class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int[] aux = new int[len + 1];
for (int i = 0; i < len; i++) {
if (citations[i] > len) {
aux[len]++;
} else {
aux[citations[i]]++;
}
}
int sum = 0;
for (int i = aux.length - 1; i >= 0; i--) {
sum += aux[i];
if (sum >= i) {
return i;
}
}
return 0;
}
}
JavaScript
排序
/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function (citations) {
citations.sort((a, b) => a - b)
for (let i in citations) {
if (citations[i] >= citations.length - i) {
return citations.length - i
}
}
return 0
}
不排序
/**
* @param {number[]} citations
* @return {number}
*/
var hIndex = function (citations) {
let aux = new Array(citations.length + 1).fill(0)
for (let x of citations) {
if (x > citations.length) {
aux[citations.length]++
} else {
aux[x]++
}
}
let sum = 0
for (let i = aux.length - 1; i >= 0; i--) {
sum += aux[i]
if (sum >= i) {
return i
}
}
return 0
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/43509.html
標籤：其他