275. H-Index II

Leetcode

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

題目

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper and citations is sorted in ascending order, 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.

You must write an algorithm that runs in logarithmic time.

Example 1:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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,2,100]
Output: 2

解答

• 方法一

這題跟上一題 274. 題目一樣，但有兩個差異點：

1. input 變成是由小到大的排序矩陣

2. 需要將時間複雜度從 O(n) 優化到 O(logn)

我們先來看一下原本 274. 題的解答再看看如何優化到 O(logn)

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;
};

原本 274. 題會先將矩陣由大排序到小，接著再從最大的值依序一直找到最小，一直找到 citations[i] < i + 1的元素，這樣的找法會花費 O(n) 的時間

但既然矩陣都排序好了，其實直接用 binary search 的方法就可以做到 O(logn) 的時間複雜度了

範例：[1, 6, 10, 100, 1000]

如果從最大依序找到最小的話要從 1000 一直找到 1 花費 O(n) 時間

但我們可以用更快的方式從中間的 10 開始找：

1. 一開始 start = 0, end = 4, mid = 2，發現 第三篇論文的引用數 10 還大於 引用次數 3 (10, 100, 1000)，代表我們還可以找到更大的 H-index 所以繼續往左找

2. start = 0, end = 3, mid = 1，發現 第二篇論文的引用數 6 還大於 引用次數 4 (6, 10, 100, 1000)，代表我們還可以找到更大的 H-index 所以繼續往左找

3. start = 0, end = 2, mid = 1，發現 第二篇論文的引用數 6 還大於 引用次數 4 (6, 10, 100, 1000)，代表我們還可以找到更大的 H-index 所以繼續往左找

4. start = 0, end = 1, mid = 0，發現 第一篇論文的引用數 1 已經小於 引用次數 5 (1, 6, 10, 100, 1000)，代表這時應該要找到更小的 H-index，所以回頭往右找

5. start = 1, end = 1, mid = 1，發現 第二篇論文的引用數 6 還大於 引用次數 4 (6, 10, 100, 1000)，代表我們還可以找到更大的 H-index 所以繼續往左找

6. start = 1, end = 0，start 已經大於 end，尋找結束，最後答案就是 5 - 1 = 4，代表從位置 1 開始的 [6, 10, 100, 1000] 這四篇論文的引用數都大於 4

var hIndex = function (citations) {
    let start = 0;
    let end = citations.length - 1;

    while (start <= end) {
        const mid = Math.floor((start + end) / 2);
        // 引用次數: citations.length - mid
        if (citations[mid] >= citations.length - mid) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return citations.length - start;
};

Runtime: 45 ms Beats 95.50% of users with JavaScript

Memory: 51.24 MB Beats 11.71% of users with JavaScript

參考資料

275. H-Index II · leetcodeleetcode.wang