LeetCode刷题记录——day1-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode刷题记录——day1。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

https://leetcode.cn/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150
注：题目有点难理解，多读几遍
可以这样考虑，建立另一个临时数组temp，当第i篇文章被引用citiations[i]次时，令j<=citiations[i]的temp[j]均加一，也就是现在对于任意j至少有temp[j]篇论文引用次数大于等于j。因为h是最大值，那么遍历temp最后一个满足temp[j]>=j的j就是所求。
当然，以上的时间复杂度和空间复杂度都比较大，另一种好的方法是先排序后遍历。
先将数组citiations进行排序，如何从大的一端向小的一端遍历，那么令h一开始为0，每当遍历到一个citiations[i]时，就说明多了一个满足条件的论文，h也就可以加一，直到"h大于citiations[i]"时，也就意味着不在存在满足条件的论文了，遍历也就结束了。
实现代码：

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int temp[5001]={0};
        int h=0;
        for(int i=0;i<citations.size();i++){
           for(int j=1;j<=citations[i];j++){
                temp[j]++;
           }
        }
        for(int i=1;i<5000;i++){
            if(temp[i]>=i){
                h=i;
            }
        }
        return h;
    }
    
};

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