274.H-Index

Tags: Medium Sort Binary Search

Links: https://leetcode.com/problems/h-index/

---

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

Example:

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

---

class Solution {
public:
    int hIndex(vector<int>& citations) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = citations.size();
        sort(citations.begin(), citations.end());
        if (!n || !citations[n - 1]) return 0;

        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (citations[mid] < n - mid) left = mid + 1;
            else right = mid;
        }

        return n - left;
    }
};

这道题如果初始数据是有序的，就是275的题目，另外这道题存在两种变形。

这道题的本质其实是个查询问题，也就是本题是单次查询，范围是整个数组，所以变换的形式就是去改变查询的范围。

一种变化是Kick start的2019 round H的第一题，同样的背景，但是需要一次输出下标从0到n-1变化时，区间[0,i]内的h值。

上面是固定了左端点，另外一种变化就是HDU 6278 Just H index，利用主席树来维护区间内的第K大值，让查询区间的左右端点都不固定。