LeetCode274.H指数

发表于 更新于 分类于 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

LeetCode274.H指数【medium】。

题目描述

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

输入输出示例

示例 1：
输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：
输入：citations = [1,3,1]
输出：1

提示：

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

题目分析

方法一：排序

我们可以将初始数组进行排序，按引用次数升序排列，将h指数初始设置为0。对于这个排序后的数组，假设当前指数是h，如果citations[i] > h，说明找到了一篇文章至少被引用了 h + 1 次，所以 h + 1，直到 h 无法再继续增大。

方法二：计数排序

根据上述解法我们发现，最终的时间复杂度与排序算法的时间复杂度有关，所以我们可以使用计数排序算法，新建并维护一个数组 counter 用来记录当前引用次数的论文有几篇。counter[i] 代表引用次数大于等于 i 的论文数目。
且依题意，h指数不能大于论文总数，所以对于超过论文总数的发表次数，我们可以将其被引用次数视为论文总数来计算，这样我们可以限制参与排序的数的范围就是 [0, n]，使得计数排序的时间复杂度降低到 O(n)。
最后我们可以从后向前遍历数组 counter，对于每个 0 ≤ i ≤ n，在数组 counter 中得到大于或等于当前引用次数 i 的总论文数。当我们找到第一个 h 指数时跳出循环（从后找到的第一个 h 必是满足条件的最大值），并返回结果。

方法三：二分

我们需要找到一个值 h，它是满足[有 h 篇论文被引用次数大于等于 h]的最大值。小于等于 h 的所有值 x 都满足这个性质，而大于等于 h 的所有值 y 都不满足这个性质，且我们可以通过较短的时间 O(n) 遍历一遍数组来判断 x 是否满足这个性质，所以可以用二分的方法来解决这个问题。
设查找范围的初始左边界 left 为 0，表示 h 指数的最小可能值为0；初始右边界 right 为 n，表示 h 指数的最大可能值为数组的长度。每次在查找范围内取中点 mid（mid 相当于当前验证的h值），同时扫描整个数组，计算大于等于 mid 的个数 cnt。如果 cnt 大于等于 mid，说明 h 可能的取值范围是 [mid, n];如果 cnt 小于 mid，说明 h 可能的取值范围是 [0, mid - 1]。

题解

题解一：排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int HIndex(int[] citations) {
    Array.Sort(citations);
    int h = 0, n = citations.Length - 1;
    for(int i = n; i >= 0; i--) {
        if(citations[i] > h) {
            h ++;
        }
        else
        {
            break;
        }
    }
    return h;
}

题解二：计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int HIndex(int[] citations) {
    int n = citations.Length, tot = 0;
    int[] counter = new int[n + 1];
    for(int i = 0; i < n; i++) {
        if(citations[i] >= n) {
            counter[n] ++;
        } else {
            counter[citations[i]]++;
        }
    }
    for(int i = n; i >- 0; i--) {
        tot += counter[i];
        if(tot >= i) {
            return i;
        }
    }
    return 0;
}

题解三：二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int HIndex(int[] citations) {
    int left = 0, right = citations.Length;
    int mid = 0, cnt = 0;
    while(left < right) {
        mid = (left + right + 1) >> 1;//向上取整避免死循环
        cnt = 0;
        for(int i = 0; i < citations.Length; i++) {
            if(citations[i] >= mid) {
                cnt++;
            }
        }
        if(cnt >= mid) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    return left;
}