Algorithm
lc274_H指数
思路:
感觉就是先排序,然后倒序模拟查看至少有i篇论文被引用 citations[i]
次.
当前ans就是 min(i, citations[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int hIndex(vector<int>& citations) {
int sz = citations.size();
int ans = 0;
sort(citations.begin(), citations.end());
for (int i = sz - 1; i >= 0; i--) {
int index = sz - i;
ans = max(ans, min(citations[i], index));
if (citations[i] < index) {
break;
}
}
return ans;
}
};
|
发现题解 还有二分,计算等方法。
其中二分和排序时间复杂度一样,但是二分的空间复杂度好一点点,计数则只需要O(n),通过计数模拟得到。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size(), tot = 0;
vector<int> counter(n + 1);
for (int i = 0; i < n; i++) {
if (citations[i] >= n) {
counter[n]++;
} else {
counter[citations[i]]++;
}
}
for (int i = n; i >= 0; i--) {
tot += counter[i];
if (tot >= i) {
return i;
}
}
return 0;
}
};
// 链接:https://leetcode.cn/problems/h-index/
|
Review
【TED演讲】工作不是你的家庭
建立工作边界,防止过度劳累导致丧失工作热情,从而过一个比较好的细水长流的工作和生活。
Tips
Rocksdb Iterator实现:从DBIter 到 TwoLevelIter 的漫长链路
Share
perf-example website share
这个网站的内容非常清晰,一张框架图更是一图胜千言,所以分享推荐。