Golang每日一练(leetDay0094) H 指数 I\II H Index

简介: Golang每日一练(leetDay0094) H 指数 I\II H Index

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.length
  • 1 <= n <= 5000
  • 0 <= 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.length
  • 1 <= n <= 10^5
  • 0 <= citations[i] <= 1000
  • citations升序排列

代码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)暂停更


目录
相关文章
|
5天前
|
Python
1167: 分离字符串(PYTHON)
1167: 分离字符串(PYTHON)
|
23天前
|
数据处理 Python
如何使用Python的Pandas库进行数据排序和排名?
Pandas在Python中提供数据排序和排名功能。使用`sort_values()`进行排序,如`df.sort_values(by=&#39;A&#39;, ascending=False)`进行降序排序;用`rank()`进行排名,如`df[&#39;A&#39;].rank(ascending=False)`进行降序排名。多列操作可传入列名列表,如`df.sort_values(by=[&#39;A&#39;, &#39;B&#39;], ascending=[True, False])`。
22 6
|
24天前
|
大数据 Python
使用Python查找字符串中包含的多个元素
本文介绍了Python中查找字符串子串的方法,从基础的`in`关键字到使用循环和条件判断处理多个子串,再到利用正则表达式`re模块`进行复杂模式匹配。文中通过实例展示了如何提取用户信息字符串中的用户名、邮箱和电话号码,并提出了优化策略,如预编译正则表达式和使用生成器处理大数据。
19 1
|
28天前
《剑指offer》——合并两个排序的链表
《剑指offer》——合并两个排序的链表
|
30天前
|
数据挖掘 开发者 Python
Python:字符串判断子串
Python:字符串判断子串
|
30天前
|
程序员 数据安全/隐私保护 Python
Python:翻转字符串
Python:翻转字符串
|
29天前
|
索引 Python
Python系列(14)—— 字符串运算符
Python系列(14)—— 字符串运算符
|
30天前
|
存储 自然语言处理 数据挖掘
Python:计算字符串中每个单词出现的次数
Python:计算字符串中每个单词出现的次数
|
30天前
|
数据可视化 数据处理 索引
Python如何对数据进行排序和排名操作?
Python如何对数据进行排序和排名操作?
29 0
|
5天前
|
Python
171: 字符串的倒序(python)
171: 字符串的倒序(python)