石家庄建工科技学院石家庄做网站,哪有免费的网站建设模板,wordpress id 连续,策略类网页游戏开服表这是索引二分的第八篇算法#xff0c;力扣链接 给你一个整数数组 citations #xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义#xff1a;h 代表“高引用次数” #xff0c;一名科研人员的 …这是索引二分的第八篇算法力扣链接 给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义h 代表“高引用次数” 一名科研人员的 h 指数 是指他她至少发表了 h 篇论文并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值h 指数 是其中最大的那个。 示例 1 输入citations [3,0,6,1,5]
输出3
解释给定数组表示研究者总共有 5 篇论文每篇论文相应的被引用了 3, 0, 6, 1, 5 由于研究者有 3 篇论文每篇 至少 被引用了 3 次其余两篇论文每篇被引用 不多于 3 次所以她的 h 指数是 3。 第一反应是看懵了第二反应是不急我们一点一点分析问题。
首先这个h不是指数组里的值数组里的值要大于等于h
然后这个h的指数是指至少发表了 h 篇论文代表一定存在len h
其次至少 有 h 篇论文被引用次数大于等于 h假设这个是个有序数组citations[len-h] h
老规矩上暴力法试试先将数组排序从右到左技术如果h citation[i] 解h
func hIndex(citations []int) int {sort.Ints(citations)result : 0for i : len(citations) - 1; i 0; i-- {if citations[i] result {result}}return result
}
这个算法的耗时瓶颈在排序算法上所以考虑不用排序该用打表的方式记录所有的次数但是怎么打表呢我们可以开一个从0~n的数组对于大于长度的数组值当n处理。打表结束之后再倒序计数比较当前的文章数和引用总次数。
func hIndex(citations []int) int {count : make([]int, len(citations)1)for _, num : range citations {if num len(citations) {count[len(citations)]} else {count[num]}}total : 0for i : len(count) - 1; i 0; i-- {total count[i]if total i {return i}}return 0
}
上面暂时都归类为暴力法回归正题我们还是得用二分法解决问题。
明确这个问题找的不是数组的值而是找的其实是数组的长度即论文个数体会一下这个问题。所以二分法来说其实也是有序的。我们根据mid的值统计符合目标的引用次数移动mid指针。
func hIndex(citations []int) int {l, r : 0, len(citations)for l r {mid : l (r-l)/2count : 0for _, num : range citations {if num mid {count}}if count mid {l mid 1} else {r mid - 1}}return l
}
