# 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](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.

&#x20;

**Example 1:**

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

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

* **方法一**

這題需要先了解一下 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&#x20;

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

```javascript
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` 所以代碼可以再簡化為：

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

Runtime: 51 ms Beats 73.97% of users with JavaScript

Memory: 48.77 MB Beats 70.34% of users with JavaScript

**參考資料**

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

**延伸問題**

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

{% embed url="<https://leetcode.com/problems/h-index-ii/description/>" %}
