274. H 指数 H Index
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义： h 代表“高引用次数”，一名科研人员的 h指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少h 次。且其余的 n - 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
提示：
n == citations.length1 <= n <= 50000 <= citations[i] <= 1000
代码1：排序
package main import ( "fmt" "sort" ) func hIndex(citations []int) int { sort.Ints(citations) n := len(citations) for i, val := range citations { if val >= n-i { return n - i } } return 0 } func main() { citations := []int{3, 0, 6, 1, 5} fmt.Println(hIndex(citations)) // 输出：3 citations = []int{1, 3, 1} fmt.Println(hIndex(citations)) // 输出：1 }
代码2：计数排序
package main import "fmt" func hIndex(citations []int) int { n := len(citations) cnt := make([]int, n+1) for _, val := range citations { if val < n { cnt[val]++ } else { cnt[n]++ } } h := 0 for i := n; i >= 0; i-- { h += cnt[i] if h >= i { return i } } return 0 } func main() { citations := []int{3, 0, 6, 1, 5} fmt.Println(hIndex(citations)) // 输出：3 citations = []int{1, 3, 1} fmt.Println(hIndex(citations)) // 输出：1 }
代码3：二分查找
package main import "fmt" func hIndex(citations []int) int { l, r := 0, len(citations)-1 n := len(citations) for l <= r { mid := l + (r-l)/2 cnt := hIndexCount(citations, citations[mid]) if cnt == citations[mid] { return cnt } else if cnt < citations[mid] { r = mid - 1 } else { if mid+1 == n || hIndexCount(citations, citations[mid+1]) < citations[mid+1] { return citations[mid] } l = mid + 1 } } return 0 } func hIndexCount(nums []int, h int) int { count := 0 for _, num := range nums { if num >= h { count++ } } return count } func main() { citations := []int{3, 0, 6, 1, 5} fmt.Println(hIndex(citations)) // 输出：3 citations = []int{1, 3, 1} fmt.Println(hIndex(citations)) // 输出：1 }
输出：
3
1
275. H 指数 II H Index ii
给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义： h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少h 次。且其余的 n - h篇论文每篇被引用次数 不超过 h次。
提示：如果 h 有多种可能的值，h 指数 是其中最大的那个。
请你设计并实现对数时间复杂度的算法解决此问题。
示例 1：
输入：citations = [0,1,3,5,6]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。
示例 2：
输入：citations = [1,2,100]
输出：2
提示：
n == citations.length1 <= n <= 10^50 <= citations[i] <= 1000citations按 升序排列
代码1：二分查找
package main import "fmt" func hIndexII(citations []int) int { n := len(citations) l, r := 0, n-1 for l <= r { mid := l + (r-l)/2 if citations[mid] >= n-mid { r = mid - 1 } else { l = mid + 1 } } return n - l } func main() { citations := []int{0, 1, 3, 5, 6} fmt.Println(hIndexII(citations)) // 输出：3 citations = []int{1, 2, 100} fmt.Println(hIndexII(citations)) // 输出：2 }
代码2：线性扫描
package main import "fmt" func hIndexII(citations []int) int { n := len(citations) h := 0 for i := n - 1; i >= 0 && citations[i] >= n-i; i-- { h = n - i } return h } func main() { citations := []int{0, 1, 3, 5, 6} fmt.Println(hIndexII(citations)) // 输出：3 citations = []int{1, 2, 100} fmt.Println(hIndexII(citations)) // 输出：2 }
输出：
3
2
🌟 每日一练刷题专栏 🌟
✨持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
Rust每日一练 专栏 （2023.5.16~）更新中... |
|
Golang每日一练 专栏 （2023.3.11~）更新中... |
|
Python每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
C/C++每日一练 专栏 （2023.2.18~2023.5.18）暂停更 |
|
Java每日一练 专栏 （2023.3.11~2023.5.18）暂停更 |
