題目： LeetCode - 274. H-Index

題目說明

給一個陣列，代表每篇論文的引用數，求 H - index。( 若 h = 5，代表有 5 篇論文的引用數大於等於 5，其餘論文的引用數皆小於 5 )

解題思路

先將陣列降冪排序，接著遍歷陣列，若 citations[i] >= i + 1，代表有 i + 1 篇論文的引用數大於等於 i + 1，持續做直到找到最大的 h 即可。( 當找到最大的 h 代表總共有 h 篇論文的引用數大於等於 h，而後面論文的引用數都小於 h )

1
2
3
4
5
6
7
8
Example:
[3,0,6,1,5]
[6,5,3,1,0] // sorted
i = 0, citations[0] = 6 >= 1, 代表目前有 1 篇論文的引用數大於等於 1
i = 1, citations[1] = 5 >= 2, 代表目前有 2 篇論文的引用數大於等於 2
i = 2, citations[2] = 3 >= 3, 代表目前有 3 篇論文的引用數大於等於 3
i = 3, citations[3] = 1 <  4, 其實做到這邊就可以停了
H - index = 3

參考解法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int h = 0, n = citations.size(), i = -1;
        sort(citations.begin(), citations.end(), greater<int>());
        while(++i < n && citations[i] >= i + 1) h = i + 1;
        // for(int i = 0; i < n; ++i) h = citations[i] >= i + 1 ? i + 1 : h;
        return h;
    }
};