咸阳公司做网站,手游app开发公司,免费看黄金的软件,网站qq访客抓取为了方便#xff0c;将 citations 记为 cs。
所谓的 h 指数是指一个具体的数值#xff0c;该数值为“最大”的满足「至少发表了 x 篇论文#xff0c;且每篇论文至少被引用 x 次」定义的合法数#xff0c;重点是“最大”。
用题面的实例 1 来举个 #x1f330;#xff0…
为了方便将 citations 记为 cs。
所谓的 h 指数是指一个具体的数值该数值为“最大”的满足「至少发表了 x 篇论文且每篇论文至少被引用 x 次」定义的合法数重点是“最大”。
用题面的实例 1 来举个 给定所有论文的引用次数情况为 cs [3,0,6,1,5]可统计满足定义的数值有哪些
h0含义为「至少发表了 0 篇且这 0 篇论文至少被引用 0 次」空集即满足恒成立
h1含义为「至少发表了 1 篇且这 1 篇论文至少被引用 1 次」可以找到这样的组合如 [3]成立
h2含义为「至少发表了 2 篇且这 2 篇论文至少被引用 2 次」可以找到这样的组合如 [3, 6]成立
h3含义为「至少发表了 3 篇且这 3 篇论文至少被引用 3 次」可以找到这样的组合如 [3, 6, 5]成立
h4含义为「至少发表了 4 篇且这 4 篇论文至少被引用 4 次」找不到这样的组合不成立
...
实际上当遇到第一个无法满足的数时更大的数值就没必要找了。一个简单的推导
至少出现 k 次的论文数不足 k 篇 至少出现 k1 次的论文必然不足 k 篇 至少出现 k1 次的论文必然不足 k1 篇即更大的 h 不满足。
二分 基于此分析我们发现对于任意的 cs论文总数量为该数组长度 n都必然对应了一个最大的 h 值且小于等于该 h 值的情况均满足大于该 h 值的均不满足。
那么在以最大 h 值为分割点的数轴上具有「二段性」可通过「二分」求解该分割点答案。
最后考虑在什么值域范围内进行二分
一个合格的二分范围仅需确保答案在此范围内即可。
再回看我们关于 h 的定义「至少发表了 x 篇论文且每篇论文至少被引用 x 次」满足条件除了引用次数还有论文数量而总的论文数量只有 n因此最大的 h 只能是 n 本身而不能是比 n 大的数否则论文数量就不够了。
综上我们只需要在 [0,n] 范围进行二分即可。对于任意二分值 mid只需线性扫描 cs 即可知道其是否合法。
代码
int hIndex(int* citations, int citationsSize) {
int left0,rightcitationsSize;int mid0,cnt0;while(leftright){// 1 防止死循环mid(leftright1)1;cnt0;for(int i0;icitationsSize;i){if(citations[i]mid){cnt;}}if(cntmid){// 要找的答案在 [mid,right] 区间内leftmid;}else{// 要找的答案在 [0,mid) 区间内rightmid-1;}}return left;}
作者宫水三叶
