LeetCode面试题Day5|LeetCode274 H指数

指路：

. - 力扣（LeetCode）274 H指数

思路与分析：

H指数，通俗来讲，将其转化为数组值与数组大小的关系。拿第一个案例[3, 0, 6, 1, 5]来看，从符合条件的元素个数入手，假设h=1，此时h指数为1，意思是该数组内有一个数大于等于1，该假设成立；那么当h=2时，意思是该数组内有一个数大于等于2，很明显该假设也成立，但第一个h=1，第二个h=2，题目明确说取最大值，那么就舍弃掉第一个h，此时h=2；继续，当h=3时，数组内有三个数大于等于3，毫无疑问，该假设也是成立的，那么本轮得到的h=3，同理，舍弃较小值，此时h=3；而假设当h=4时，意为给定数组中有4个元素的值大于等于4，那么事实上大于4的只有5和6两个元素不符合当前h=4的条件，因此该假设不成立；同理当4不满足时就没有必要往后假设了，因为只会有更少的元素值大于等于5及以上。以上就是我们初步的模拟思路。那么进入解题阶段，多样例多元素总不能一直假设，那么尝试让元素跳过假设，也就是说在数组中越大的元素越容易被满足，至于比它小的数再判断即可。那么首先将数组sort排序，得到一个非递减序列，从后往前遍历，如果遍历到的数值大于h则说明该元素符合条件，此时h增1。

代码：

class Solution {
public:
    int hIndex(vector<int>& citations) {
    sort(citations.begin(), citations.end());
    // [0, 1, 3, 5, 6]
    int n = citations.size();
    int i = n - 1;
    int h = 0;  // 最后的h指数
    for (int i = n - 1; i >= 0; --i) {// 本轮符合条件的个数
        if (citations[i] > h) {
            h++;
        }
    }
    return h;
    }
};