?LeetCode刷題實(shí)戰(zhàn)274：H指數(shù)
Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return compute the researcher's h-index.
According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n ? h papers have no more than h citations each.
If there are several possible values for h, the maximum one is taken as the h-index.
示例
輸入：citations = [3,0,6,1,5]
輸出：3
解釋：給定數(shù)組表示研究者總共有 5 篇論文，每篇論文相應(yīng)的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇論文每篇 至少 被引用了 3 次，其余兩篇論文每篇被引用 不多于 3 次，所以她的 h 指數(shù)是 3。
解題
class Solution {
public:
int hIndex(vector<int>& citations) {
int citationsSize = citations.size();
vector<int> dp(citationsSize + 1, 0);//用于記錄大于等于i的論文被引用的多少次
for (auto num : citations) {
if (num > citationsSize) {//這篇論文引用超過(guò)citationsSize也只能記作被引用了citationsSize次（因?yàn)镠指數(shù)不會(huì)大于論文的總數(shù)）
dp[citationsSize] += 1;
}
else {//在界限內(nèi)直接自增
dp[num] += 1;
}
}
//因?yàn)樾枰易畲蟮腍值，所以需要從后往前掃描
//判斷是否所有的論文引用次數(shù)都大于等于citationsSize次
if (dp[citationsSize] >= citationsSize) {
return citationsSize;
}
//然后從后往前開(kāi)始掃描（動(dòng)態(tài)規(guī)劃）
for (int i = citationsSize - 1; i >= 0; --i) {
dp[i] += dp[i + 1];//引用次數(shù)大于等于i + 1次的肯定 大于i次，所以需要加上（比如示例中引用次數(shù)為6的計(jì)算為超過(guò)3次的）
if (dp[i] >= i) {//判斷是否達(dá)到H指數(shù)的標(biāo)準(zhǔn)
return i;
}
}
return 0;
}
};