# 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](https://en.wikipedia.org/wiki/H-index): 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.

&#x20;

**Example 1:**

<pre><code><strong>Input: citations = [0,1,3,5,6]
</strong><strong>Output: 3
</strong><strong>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.
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: citations = [1,2,100]
</strong><strong>Output: 2
</strong></code></pre>

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

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

1. input 變成是由小到大的排序矩陣
2. 需要將時間複雜度從 O(n) 優化到 O(logn)

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

```javascript
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

```javascript
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

**參考資料**

{% embed url="<https://leetcode.wang/leetcode-275-H-IndexII.html>" %}

{% embed url="<https://www.youtube.com/watch?v=l9SHuROcR-Y>" %}
