Contents

ARST打卡第234周[234/521]

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

这个网站的内容非常清晰,一张框架图更是一图胜千言,所以分享推荐。