[LeetCode] 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.”

For example, given citations = [3, 0, 6, 1, 5], which 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, his h-index is 3.

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

大意

N张paper,如果每张papaer有至少h次索引,而其他N - h张paper没有那么超过h次索引(小于),那么h-index等于h,多个h-index取最大值

解法一

排序,模拟题目要求,index大于等于reference的数量

AC代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        if (n == 0) return 0;
        sort(citations.begin(), citations.end(), greater<int>());
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (i >= citations[i]) {
                return i;
            }
        }
        return n;
    }
};

解法二,优化解法一

大于n的值其实我们都可以按照N算,因为h-index不会超过N,用一个长度为N + 1的数组保存每个index的不小于这个index的paper引用数
注意比index大的引用数是从N到0递增的

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int cnts[n + 1];
        memset(cnts, 0, sizeof cnts);
        for (int i = 0; i < n; i++) {
            if (citations[i] > n)
                cnts[n]++;
            else
                cnts[ citations[i] ]++;
        }
        int sum = 0;
        for (int i = n; i > 0; i--) {
            if (cnts[i] + sum >= i) {
                return i;
            }
            sum += cnts[i];
        }
        return 0;
    }
};

超级不习惯新电脑的快捷键。。。估计要适应好一段时间