8000 add the 275 solution · Feng2012/awesome-golang-leetcode@dd5b15d · GitHub
[go: up one dir, main page]
Skip to content

Commit dd5b15d

Browse files
author
Wave
committed
add the 275 solution
1 parent 8846aa9 commit dd5b15d

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+
func hIndex(citations []int) int {
45+
if len(citations) == 0 {
46+
return 0
47+
}
48+
l, r := 0, len(citations)-1
49+
for l < r {
50+
mid := (l + r) / 2
51+
if len(citations)-mid <= citations[mid] {
52+
r = mid
53+
} else {
54+
l = mid + 1
55+
}
56+
}
57+
if citations[l] <= len(citations) {
58+
return len(citations) - l
59+
}
60+
return 0
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+
func hIndex(citations []int) int {
4+
if len(citations) == 0 {
5+
return 0
6+
}
7+
l, r := 0, len(citations)-1
8+
for l < r {
9+
mid := (l + r) / 2
10+
if len(citations)-mid <= citations[mid] {
11+
r = mid
12+
} else {
13+
l = mid + 1
14+
}
15+
}
16+
if citations[l] <= len(citations) {
17+
return len(citations) - l
18+
}
19+
return 0
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+
func TestSolution(t *testing.T) {
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs []int
14+
expect int
15+
}{
16+
{"TestCase", []int{0, 1, 3, 5, 6}, 3},
17+
}
18+
19+
// 开始测试
20+
for i, c := range cases {
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+
func BenchmarkSolution(b *testing.B) {
33+
34+
}
35+
36+
// 使用案列
37+
func ExampleSolution() {
38+
39+
}

0 commit comments

Comments
 (0)
0