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.

二. 題目分析

首先需要了解一下題目的大意：

給定一個數組，記載了某研究人員的文章引用次數（每篇文章的引用次數都是非負整數），編寫函數計算該研究人員的h指數。

根據維基百科上對h指數的定義：“一名科學家的h指數是指在其發表的

N

篇論文中，有

h

篇論文分别被引用了至少

h

次，其餘

N-h

篇的引用次數均不超過

h

次”。

例如，給定一個數組

citations = [3, 0, 6, 1, 5]

，這意味着該研究人員總共有

5

篇論文，每篇分别獲得了

3, 0, 6, 1, 5

次引用。由于研究人員有

3

篇論文分别至少獲得了

3

次引用，其餘兩篇的引用次數均不超過

3

次，因而其h指數是

3

。

注意：如果存在多個可能的

h

值，取最大值作為

h

指數。

通過下圖，可以更直覺了解

h

值的定義，對應圖中，即是球左下角正方形的最大值：

以下解釋中，假設給定數組的大小為

N

，即共有

N

篇文章。

正常的做法有兩種，也是題目tips中提到的，首先想到的是将數組進行排序，然後從後往前周遊，找出這個h值，該方法的複雜度是：

O(n*logn)

。

在面試中，若允許使用輔助記憶體，可以使用第二種方法，即開辟一個新數組

record

，用于記錄

0~N

次引用次數的各有幾篇文章（引用次數大于

N

的按照

N

次計算）周遊數組，統計過後，周遊一次統計數組

record

，即可算出

h

值的最大值。時間複雜度為

O(n)

。

三. 示例代碼

// 排序+周遊
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), [](const int &a, const int &b){return a > b; });
        int i = ;
        for (; i < citations.size(); ++i)
            if (citations[i] <= i)
                break;
        return i;
    }
};
           

// 第二種的方法
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int citationSize = citations.size();
        if (citationSize < ) return ;
        vector<int> record(citationSize + , );
        for (int i = ; i < citationSize; ++i)
        {
            if (citations[i] <= citationSize)
                ++record[citations[i]];
            else
                ++record[citationSize];
        }

        for (int j = citationSize, paperNum = ; j >= ; --j)
        {
            paperNum += record[j];
            if (paperNum >= j) return j;
        }
        return ;
    }
};
           

四. 小結

使用何種方法，需要根據實際條件而定。