Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitdd5b15d

Browse files
author
Wave
committed
add the 275 solution
1 parent8846aa9 commitdd5b15d

File tree

3 files changed

+134
-0
lines changed

3 files changed

+134
-0
lines changed

‎src/0275.H-Index-II/README.md

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
#[275. H-Index II][title]
2+
3+
##Description
4+
5+
给定一个科研工作者的一系列论文的引用次数（引用次数是非负整数），已经从小到大排好序，请计算他的h因子。
6+
7+
h因子的定义：一个科学家如果有 hh 篇文章的引用次数至少是 hh，并且其他文章的引用次数不超过 hh，我们就说他的影响因子是 hh。
8+
9+
注意： 如果一个人有多个可能的 hh，返回最大的 hh 因子。
10+
进一步：
11+
12+
这道题目是 LeetCode 274. H-Index的升级版，citations 保证是严格递增的；
13+
你能否给出时间复杂度是 O(logn)O(logn) 级别的算法？
14+
15+
**Example 1:**
16+
17+
```
18+
Input: citations = [0,1,3,5,6]
19+
Output: 3
20+
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had
21+
received 0, 1, 3, 5, 6 citations respectively.
22+
Since the researcher has 3 papers with at least 3 citations each and the remaining
23+
two with no more than 3 citations each, her h-index is 3.
24+
```
25+
26+
**Tags:** Math, String
27+
28+
##题意
29+
>(二分) O(logn)O(logn)
30+
由于数组是从小到大排好序的，所以我们的任务是：
31+
在数组中找一个最大的 hh，使得后 hh 个数大于等于 hh。
32+
我们发现：如果 hh 满足，则小于 hh 的数都满足；如果 hh 不满足，则大于 hh 的数都不满足。所以具有二分性质。
33+
直接二分即可。
34+
时间复杂度分析：二分检索，只遍历 lognlogn 个元素，所以时间复杂度是 O(logn)O(logn)
35+
36+
##题解
37+
38+
###思路1
39+
>。。。。
40+
41+
```go
42+
package main
43+
44+
funchIndex(citations []int)int {
45+
iflen(citations) ==0 {
46+
return0
47+
}
48+
l,r:=0,len(citations)-1
49+
for l < r {
50+
mid:= (l + r) /2
51+
iflen(citations)-mid <= citations[mid] {
52+
r = mid
53+
}else {
54+
l = mid +1
55+
}
56+
}
57+
if citations[l] <=len(citations) {
58+
returnlen(citations) - l
59+
}
60+
return0
61+
}
62+
```
63+
64+
###思路2
65+
>思路2
66+
```go
67+
68+
```
69+
70+
##结语
71+
72+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
73+
74+
[title]:https://leetcode.com/problems/h-index-ii/
75+
[me]:https://github.com/kylesliu/awesome-golang-leetcode

‎src/0275.H-Index-II/Solution.go

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package Solution
2+
3+
funchIndex(citations []int)int {
4+
iflen(citations)==0 {
5+
return0
6+
}
7+
l,r:=0,len(citations)-1
8+
forl<r {
9+
mid:= (l+r)/2
10+
iflen(citations)-mid<=citations[mid] {
11+
r=mid
12+
}else {
13+
l=mid+1
14+
}
15+
}
16+
ifcitations[l]<=len(citations) {
17+
returnlen(citations)-l
18+
}
19+
return0
20+
}

‎src/0275.H-Index-II/Solution_test.go

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
funcTestSolution(t*testing.T) {
10+
//测试用例
11+
cases:= []struct {
12+
namestring
13+
inputs []int
14+
expectint
15+
}{
16+
{"TestCase", []int{0,1,3,5,6},3},
17+
}
18+
19+
//开始测试
20+
fori,c:=rangecases {
21+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
22+
got:=hIndex(c.inputs)
23+
if!reflect.DeepEqual(got,c.expect) {
24+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
25+
c.expect,got,c.inputs)
26+
}
27+
})
28+
}
29+
}
30+
31+
//压力测试
32+
funcBenchmarkSolution(b*testing.B) {
33+
34+
}
35+
36+
//使用案列
37+
funcExampleSolution() {
38+
39+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp