leetcode 274 H-Index
Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.
According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."
For example, given
citations = [3, 0, 6, 1, 5]
, which means the researcher has5
papers in total and each of them had received3, 0, 6, 1, 5
citations respectively. Since the researcher has3
papers with at least3
citations each and the remaining two with no more than3
citations each, his h-index is3
.Note: If there are several possible values for
h
, the maximum one is taken as the h-index.Hint:
- An easy approach is to sort the array first.
- What are the possible values of h-index?
- A faster approach is to use extra space.
题目地址: leetcode H-Index
题意:
给定一个数组代表论文被引用次数。要求计算h-index。
h-index定义如下:
一个学者发表的n篇论文中,他有h篇被引用至少h次,而其他的n-h篇被引用次数都不超过h。
思路:
显然,答案的范围为[0,n],n为数组的长度。
方法一
从高到底排序,然后对排完序的数组扫描。
对于i,h-index为min(i,citations[i])
C++
1 | class Solution { |
Python
1 | class Solution(object): |
也可以
1 | class Solution(object): |
如果不倒着排,则可以这么写:
n - i 是大于引用数citations[i]
的个数。
对于i,h-index 为min(n - i,citations[i])
C++
1 | class Solution { |
Python
1 | class Solution(object): |
方法二
对引用数进行计数。这样就不需要排序啦~
1 | class Solution(object): |
leetcode 275 H-Index II
Follow up for H-Index: What if the
citations
array is sorted in ascending order? Could you optimize your algorithm?Hint:
- Expected runtime complexity is in O(log n) and the input is sorted.
题目地址: leetcode H-Index II
题意:
就是要求时间复杂度为O(log n) 的H-Index,数组已经升序排好
思路:
二分,枚举答案[0,n]
1 | class Solution(object): |