問題
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."
Note: If there are several possible values for h, the maximum one is taken as the h-index.
例子
For example, given citations = [3, 0, 6, 1, 5], which 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, his h-index is 3.
分析
題目有點(diǎn)繞近范，通俗點(diǎn)理解就是：有一個(gè)數(shù)組A，大小為n⊙有罚現(xiàn)在要找一個(gè)數(shù)h顺又，使得A有至少h個(gè)元素不小于h。
現(xiàn)假設(shè)數(shù)組為[3, 0, 6, 1, 5]等孵。
方法一：將數(shù)組從小到大排序稚照，然后從大到小（n-->0）枚舉h值俯萌，再計(jì)算數(shù)組中不小于h的元素個(gè)數(shù)果录。數(shù)組排序后為[0, 1, 3, 5, 6]。假設(shè)h=5咐熙，不小于5的元素個(gè)數(shù)為2弱恒，2<5，不滿足要求棋恼；h=4返弹，不小于4的元素個(gè)數(shù)為2，仍不滿足要求爪飘；h=3义起，不小于3的元素個(gè)數(shù)為3，3>=3师崎，滿足要求默终，所以h=3。在排序數(shù)組中計(jì)算不小于某個(gè)數(shù)的元素個(gè)數(shù)可以使用stl的lower_bound函數(shù)，時(shí)間復(fù)雜度為O(logn)齐蔽。再加上之前的排序两疚，總的復(fù)雜度為O(nlogn)。
方法二：將數(shù)組從大到小排序含滴，然后找到一個(gè)最大的數(shù)組下標(biāo)诱渤，該下標(biāo)對(duì)應(yīng)的元素大于該下標(biāo)。數(shù)組排序后為[6, 5, 3, 1, 0]谈况。滿足條件的下標(biāo)為3源哩，所以h=3。因?yàn)閿?shù)組從大到小排序鸦做，假設(shè)下標(biāo)為i，i其實(shí)就等于數(shù)組中不小于A[i]的元素的個(gè)數(shù)谓着。當(dāng)A[i]>=i時(shí)泼诱，則必然有A存在至少i個(gè)元素不小于i。由于需要排序赊锚，時(shí)間復(fù)雜度為O(nlogn)治筒。
方法三：其實(shí)我們不需要將數(shù)組排序∠掀眩考慮有n+1個(gè)bucket耸袜，編號(hào)為0到n。遍歷數(shù)組牲平，如果數(shù)組元素a不小于n堤框，bucket[n]加1；如果數(shù)組元素小于n纵柿，bucket[a]加一蜈抓。接著定義一個(gè)total變量，從后往前累加bucket昂儒，如果total大于等于bucket下標(biāo)i沟使，則h=i。實(shí)際上total的含義的就是數(shù)組中不小于第i個(gè)元素的個(gè)數(shù)渊跋。
數(shù)組為[3, 0, 6, 1, 5]腊嗡，bucket初始化為[0, 0, 0, 0, 0]，計(jì)數(shù)之后為[1, 1, 0, 1, 0, 2]拾酝。當(dāng)i=5時(shí)燕少，total=2, 2<5，不滿足要求蒿囤；i=4棺亭，total=2+0=2<4，不滿足要求；i=3镶摘，total=2+1=3>=3嗽桩，滿足要求。因此h=3凄敢。由于該方法不需要排序碌冶，只變量了兩次數(shù)組，因此時(shí)間復(fù)雜度為O(n)涝缝。
要點(diǎn)
bucket sort. 大于n的元素被壓縮到第n個(gè)bucket里扑庞。
時(shí)間復(fù)雜度
O(n)
空間復(fù)雜度
O(n)
代碼
方法一
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end());
for (int i = citations.size(); i >= 0; i--) {
if (lower_bound(citations.begin(), citations.end(), i) - citations.begin() <= citations.size() - i)
return i;
}
return 0;
}
};
方法二
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end(), greater<int>());
for (int i = citations.size(); i >= 1; i--) {
if (citations[i - 1] >= i)
return i;
}
return 0;
}
};
方法三
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(), count = 0;
vector<int> bucket(n + 1, 0);
for (int c : citations)
bucket[min(c, n)]++;
for (int i = n; i >= 0; i--) {
count += bucket[i];
if (count >= i) return i;
}
return 0;
}
};
