打卡记录

H 指数（二分）

链接

以最大值 x 为分割点的正整数数轴上，满足：

• 少于等于 x 的数值必然满足条件；
• 大于 x 的数值必然不满足。
  采用右边界二分查找，寻找满足条件的最大 H 指数要求。

class Solution {
public:int hIndex(vector<int>& citations) {int n = citations.size();auto check = [&](int mid) -> bool {int cnt = 0;for (int i = 0; i < n; ++i)if (citations[i] >= mid) cnt++;return cnt >= mid;};int l = 0, r = n;while (l < r) {int mid = (l + r + 1) / 2;if (check(mid)) l = mid;else r = mid - 1;}return l;}
};

H 指数 II（二分）

链接

由于数组按照顺序排序，因此满足：

如果数组升序，在最大的符合条件的分割点 x 的右边（包含分割点），必然满足 citations[i]>=x，我们应当对其进行计数，对于分割点的左边，必然不满足 citations[i]>=x，无需进行计数。

由于是从右边开始的满足条件，这里使用左边界二分查找，来寻找最大 H 指数。

class Solution {
public:int hIndex(vector<int>& citations) {int n = citations.size(), l = 0, r = n;while (l < r) {int mid = l + (r - l) / 2;if (citations[mid] >= n - mid) r = mid;else l = mid + 1;}return n - l;}
};