leetcode_274 H指数

1. 题意

在数组中找到最大的k, 使得至少k个数不小于k。

H指数

2. 题解

2.1 排序

从大到小排序完后，直接模拟即可。

class Solution {
public:int hIndex(vector<int>& citations) {sort( citations.begin(), citations.end() );int res = 0;int cur = citations.size() - 1;while ( cur > -1) {if (res + 1 > citations[cur])break;++res;--cur;}return res;}
};

2.2 计数排序

假设共发表了k篇论文，则H指数最大值为k;再看数据范围则可以缩小，用计数排序进行统计结果，最后从后往前遍历，当累计的论文数大于当前idx, 则返回结果。

class Solution {
public:int hIndex(vector<int>& citations) {int sz = citations.size();int arr[5000+1];memset(arr, 0, sizeof(arr));for (auto &v: citations) {if (v > sz)arr[sz]++;elsearr[v]++;}int res = 0;int cnt = 0;for (int i = sz; i > 0; --i) {cnt += arr[i];if ( cnt >= i ) {res = i;break;}}return res;}
};

2.3 二分查找

由于答案在一定范围，所以可以二分答案，每次判断是否满足H指数的定义。

class Solution {
public:int hIndex(vector<int>& citations) {int sz = citations.size();int l = 0;int r = sz;int ans = 0;function<int(const vector<int> &, int)>p = [&](const vector<int> &arr, int b)->int{int ans = 0;for (auto v:arr)if (v >= b)++ans;return ans;};while ( l < r) {int mid = l + (r - l + 1 >> 1);int cnt = p(citations, mid);if ( cnt >= mid )l = mid;elser = mid - 1;}return l;}
};