【leetcode】274. H指数

本题的代码实测正确，但思路分析部分个人感觉还有点含糊，请谨慎查看思路分析部分。

题目内容

274.H指数

思路分析

本题首先需理清H指数的概念，官方题解中的图片可以帮助理解此概念（个人感觉这个是本题最难的点，非常绕）。H指数即为图中直方图上最大正方形的边长h。

理解H指数的概念后，共有两种思路解决此问题。两种思路都是采用了先排序再遍历找到H指数的思想。

思路一

使用快速排序将citations数组按从小到大的顺序进行排序。这里为了练习，自己实现了快排算法。
从引用次数较小的文章开始，依次递增文章序号i，则此时当前遍历文章+剩余未被遍历的文章数remain_paper_num为paper_num - i。
当当前文章的引用次数citations[i]大于等于remain_paper_num时，证明找到了H指数，H指数为remain_paper_num。

思路二

思路二比较巧妙，利用了如下特性来使用一种此种情况下更快的排序：计数排序。

如果一篇文章的引用次数超过论文的总数 n，那么将它的引用次数降低为 n 也不会改变 h 指数的值。

建立一个大小为论文总数+1的计数数组（因为引用次数为0也需要计数排序），并进行计数排序。
将引用次数从高至低进行遍历，找到H指数。

详见本题的官方题解。

代码

#include <vector>
#include <string>

using namespace std;

int Partition(vector<int> &a, int low, int high) {
    int pivot = a[low];
    while (low < high) {
        // 在基准的右边寻找小于等于基准的数，发现后交换至左边
        while (low < high && a[high] >= pivot) {
            --high;
        }
        a[low] = a[high];
        // 在基准的左边寻找比基准大的数，发现后交换至右边
        while (low < high && a[low] <= pivot) {
            ++low;
        }
        a[high] = a[low];
    }
    // 将基准置于i=j处
    a[low] = pivot;
    return low;
}

void QuickSort(vector<int> &a, int low, int high) {
    if (low < high) {
        int pivot_index = Partition(a, low, high);
        QuickSort(a, low, pivot_index - 1);
        QuickSort(a, pivot_index + 1, high);
    }
}

int min(int a, int b) {
    if (a > b)
        return b;
    else
        return a;
}

class Solution {
public:
    // 自己解法：快排+线性查找（与官方解法一相同）
    // 缺点是快排的空间复杂度为O(log n)，
    // 而一般语言内置的是堆排序，空间复杂度为O(1)
    // 时间复杂度：O(nlog n),空间复杂度：O(1)
    int hIndex1(vector<int>& citations) {
        QuickSort(citations, 0, citations.size() - 1);
        
        int h_index{ 0 };
        int paper_num = citations.size();
        
        for (int i = 0; i < paper_num; ++i) {
            int at_least_cit_paper_num = paper_num - i;
            // 当前论文引用次数大于等于at_least_cit_paper_num，
            // 则证明有at_least_cit_paper_num篇论文至少被引用了at_least_cit_paper_num次
            if (citations[i] >= at_least_cit_paper_num) {
                // 由于已经排好序，因此新得出的h指数总是最大的
                // (at_least_cit_paper_num在不断减小)
                h_index = at_least_cit_paper_num;
                break;
            }
        }

        return h_index;
    }

    // 官方解法二：使用计数排序https://leetcode-cn.com/problems/h-index/solution/hzhi-shu-by-leetcode/
    // 时间复杂度：O(n),空间复杂度：O(n)
    int hIndex2(vector<int>& citations) {
        int paper_num = citations.size();
        // 创建一个大小为paper_num+1的计数数组
        // 大小为paper_num+1的原因是引用次数为n需要占用数组的第n个位置
        // 故需要0~n共n+1个位置
        vector<int> count;
        count.resize(paper_num + 1);  // 改变容器大小，默认用0填充。
        // 计数
        for (auto c : citations) {
            count[min(c, paper_num)]++;
        }
        
        // 倒着查找
        int citation_num{ paper_num }; 
        for (int at_least_cit_paper_num = count[paper_num];  // at_least_cit_paper_num
                                                             // 表示至少有citation_num次引用的论文数量
                citation_num > at_least_cit_paper_num;  // 当引用数小于等于at_least_cit_paper_num时终止
                at_least_cit_paper_num += count[citation_num]) {
            citation_num--;
        }

        return citation_num;
    }
};


int main() {
    Solution s;
    vector<int> input{ 1,2,2,2,4,4,4 };
    
    int output{ 0 };
    output = s.hIndex2(input);

    return output;
}