算法练习13——H 指数

LeetCode 274 H 指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。

蛮力法：排序然后计数

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort()
        n = len(citations)
        h = 0
        res = 0
        t = 0
        for i in range(n - 1, -1, -1):
            if citations[i] != res:
                h = max(h, min(res, t))
                res = citations[i]
                t = n - i
            else:
                t += 1
        h = max(h, min(res, t))
        return h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以换一种思路

首先对数组进行排序，然后h的最大值肯定是发表的论文数n，最少是0；那么h从n开始往下遍历，根据h指数的定义，一定要有h篇论文的引用次数大于等于h，那么直接查看下标为n-h的论文的引用次数，因为这篇论文后面（包括它自己）的数量为h，如果这篇论文的引用次数小于h，说明这个h是不满足条件的，反之则直接返回。

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        Arrays.sort(citations);
        int h = n;
        while(h > 0){
            if(citations[n-h] >= h) return h;
            h--;
        }
        return 0;
    }
}

// 作者：卷不动啦
// 链接：https://leetcode.cn/problems/h-index/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

分治法，二分查找h

主要思路是在 0,len(citations) 中二分查找h，0,len(citations) 中的元素是否是最终的h每次判断一个元素要遍历一次数组计数看看是否满足条件，时间复杂度就是O(nlogn)

我们需要找到一个值 h，它是满足「有 h 篇论文的引用次数至少为 h」的最大值。小于等于 h 的所有值 x 都满足这个性质，而大于 h 的值都不满足这个性质。同时因为我们可以用较短时间（扫描一遍数组的时间复杂度为 O(n)O(n)O(n)，其中 nnn 为数组 citations\textit{citations}citations 的长度）来判断 x 是否满足这个性质，所以这个问题可以用二分搜索来解决。
设查找范围的初始左边界 leftleftleft 为 000，初始右边界 rightrightright 为 nnn。每次在查找范围内取中点 midmidmid，同时扫描整个数组，判断是否至少有 mid 个数大于 mid。如果有，说明要寻找的 h 在搜索区间的右边，反之则在左边。

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        left,right = 0,len(citations)
        while left<right:
            # +1 防止死循环
            mid = (left+right+1)>>1
            cnt = 0
            for v in citations:
                if v>=mid:
                    cnt+=1
            if cnt>=mid:
                # 要找的答案在 [mid,right] 区间内
                left=mid
            else:
                # 要找的答案在 [0,mid) 区间内
                right=mid-1
        return left

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/h-index/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22