博文中会简要介绍Leetcode P0274题目分析及解题思路。

“H-Index”是一道中等男的的题目，这道题想法比较直观，主要思路是排序后计数。

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

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

如何思考这道题？

一般地说，遇到类似的这类统计或者计数问题，应当想到或许能够利用排序来降低计数的难度。尤其像p0274这样的乍一眼看上去并没有什么计数规律的题目，即便可能存在时间复杂度为O(n)的算法，但在没有头绪之前，可以利用排序先尝试寻找规律。

当我们首先将所有的文章按citations从小到大排序后，不难得到下图。从下图中我们可以很直观地看出，H-index应当是图示中虚线和直方图相交与不相交的临界处的h的值。

那么此时的思路就很简单了，排序后找到这个临界点即可。

基本思路

首先对所有文章按citations从小到大排序。然后可以利用二分搜索找到临界点，也可以按序从头扫描一遍来寻找临界点。

而临界点的特点则是，h的值恰好大于或者等于当前扫描到的文章的citations的值。前者（大于）则应当返回h-1，后者（等于）应当直接返回h。

以下是Java的题解代码实现。

class Solution {
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        
        int hIndex = 0, N = citations.length;
        for (int i=N-1; i>=0; --i) {
            hIndex++;
            
            if (hIndex == citations[i])
                return hIndex;
            else if (hIndex > citations[i])
                return hIndex-1;
        }
        
        return hIndex;
    }
}

以下是C++的题解代码实现。

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