274. H-Index

Leetcode

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

題目

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

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

Example 1:

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, their h-index is 3.

Example 2:

Input: citations = [1,3,1]
Output: 1

解答

• 方法一

這題需要先了解一下 H-index 到底是什麼東西，我們先從範例 1. 來看，[3, 0, 6, 1, 5] 排序過後是 [6, 5, 3, 1, 0]，這代表了其中有三篇論文的引用數大於 3，分別是 [6, 5, 3]。

到這邊為止其實題目就差不多解出來了，我們可以先用 count 代表引用數，之後隨著每次的遍歷元素count 都會加 1，接著只要看 論文的引用數(元素數值) 大於 count，代表還可以讓 count 繼續變大，直到 論文的引用數(元素數值) 小於 count 的時候，這時的 count - 1 代表的就是 H-index 了

範例：[6, 5, 3, 1, 0]

一開始 count = 1，第一篇論文引用數 6 大於 1，將引用數 +1 後繼續遍歷

count = 2，第二篇論文引用數 5 大於 2，將引用數 +1 後繼續遍歷

count = 3，第三篇論文引用數 3 等於 3，將引用數 +1 後繼續遍歷

count = 4，第四篇論文引用數 1 小於 4

此時的 count - 1 = 3 就是想求的 H-index，代表著總共有三篇論文的引用數大於 3

var hIndex = function (citations) {
    // 大排到小
    citations.sort((a, b) => b - a);

    // 引用數
    let count = 1;
    for (i = 0; i < citations.length; i++) {
        // 某篇論文的引用數大於當前引用數
        if (citations[i] >= count) {
            count++;
        } else {
            break;
        }
    }

    return count - 1;
};

Runtime: 56 ms Beats 49.24% of users with JavaScript

Memory: 48.98 MB Beats 56.75% of users with JavaScript

但仔細一看我們可以發現，遍歷過程中 count 都會是 i + 1 所以代碼可以再簡化為：

var hIndex = function (citations) {
    citations.sort((a, b) => b - a);

    for (i = 0; i < citations.length; i++) {
        if (citations[i] < i + 1) {
            return i;
        };
    }

    return i;
};

Runtime: 51 ms Beats 73.97% of users with JavaScript

Memory: 48.77 MB Beats 70.34% of users with JavaScript

參考資料

274. H-Index · leetcodeleetcode.wang

延伸問題

方法 1. 的時間複雜度是 O(n)，有沒有辦法將時間複雜度優化成 O(log n) 呢？這個就是下一題 275. 的要求

H-Index II - LeetCodeLeetCode