免费招聘网站有哪些,网站运营公司哪家效果好,株洲人才网,百度代理推广H指数
1 题目描述
https://leetcode.cn/problems/h-index/
给你一个整数数组 citations #xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义#xff1a;h 代表“高引用次数” #xff0c;一…H指数
1 题目描述
https://leetcode.cn/problems/h-index/
给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 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。
示例 2
输入citations [1,3,1] 输出1 2 思路
反正不是我想出来的随便写写
解题方法来源
这道题也是一道“翻译不当人”的典范我们可以将这句话重新翻译一下 找到一个阈值h数组中大于等于h的元素数量也大于等于h。同时保证阈值为h1的时候找不到足够数量的元素个数。 然后我们更加格式化地理解一下上面这句话假设有一个统计函数counter(c)来统计数组中大于等于c的元素个数counter(h) h, counter(h1) h1。
比如我们设citations[13, 7, 6, 18, 12, 20, 20, 3, 0, 7]我们用gif的形式来表现当c1、2、3...10的时候数组中满足条件的元素个数。 counter(1) 9 1
counter(2) 9 2
counter(3) 9 3
counter(4) 8 4
counter(5) 8 5
counter(6) 8 6
counter(7) 7 7
-------------------
counter(8) 5 8
counter(9) 5 9
counter(10) 5 10我们用下图表示 假设我们有一个数组[1, 2, ... , len(citiations)]设为nums其中一定有一个分界线h左和右分别表示满足或者不满足条件。
而当我们将上述数组替换成counter(c)即counters 很明显counters数组是一个有序的、递减的数组。 好像事情朝着有趣的方向发展了我们有一个有序数组counters我们有一个判定条件counters[i] i1i在这里是下标我们需要从有序数组中找到最后一个符合条件的元素。 But, 如果我们对[1, 2, ... , len(citiations)]设为nums数组进行遍历对每个元素都施加counter函数来获得最终的counters数组太耗时了。我们看看能不能对上面的表述进行一些改造毕竟nums和counters是一一对应的我们可以在遍历到nums对应的元素时再计算对应的counter
我们有一个有序数组[1, 2, … , len(citiations)]表示为nums我们有一个判定条件counter(nums[i]) i1i在这里是下标我们需要从有序数组中找到最后一个符合条件的元素。
在二分法中我比较喜欢直接使用第1个元素、第2个元素、……、第n个元素这样的方式来指示元素的位置。
二分法中具有两个关键问题
mid元素的下标计算left指针和right指针的跳转方式
mid的计算其实和left以及right指针的跳转方式相关。比如我们这个题目中需要找到最后一个符合条件的元素。
也就是说假设counter(nums[mid]) nums[mid]我们知道nums[mid]满足条件但是nums[mid1]还满足吗不一定所以left就 不能 直接跳转到mid的右边而是 只能 直接跳转到mid上。 if (counter(cs, nums[mid_index]) nums[mid_index]) {l real_mid;} else {r real_mid - 1;}那么我们如何计算mid呢这就需要我们考虑当只剩下两个元素的时候mid到底是在left上还是在right上。如果让midleft下一步如果left需要跳转leftmid然后midleft。。。。。。无限循环。
所以我们先看怎么跳转再回过头想怎么计算mid。
也就是说如果当前的[left~right]之间的元素个数为偶数我们需要让mid指针指向中间两个元素的后一个元素。
class Solution {public int hIndex(int[] cs) {int[] nums new int[cs.length];for (int i 0; i cs.length; i) {nums[i] i 1;}int l 1;int r cs.length;while (l r) {int mid_index ((l r) / 2); // 注意我们这里的l和r都是元素的真实位置从1开始而不是索引从0开始// (l r) / 2 在奇数情况下是中间元素的位置// 偶数情况下是两个中间元素的前一个同时也是后一个元素在数组中的索引位置。int real_mid mid_index 1; // 中间两个元素中后一个的元素的真实位置if (counter(cs, nums[mid_index]) nums[mid_index]) {l real_mid; // left转移到mid} else {r real_mid - 1; // right转移到mid - 1}}return counter(cs, l) l ? l : 0; // 有两种情况一个是cs中只有一个元素另一种情况是所有元素都为0}int counter(int[] cs, int mid) {int ans 0;for (int i : cs) if (i mid) ans; // 计算citiations中大于等于mid的元素数量。return ans;}
}
