274.h-index
Sort then iterate, runtime 97.36%
Published in
2 min readApr 6, 2019
Solution 1: sort then iterate
Some points:
# first point[0, 1, 3, 5, 6]5 0 # there are 5 papers have citations 0
4 1 # there are 4 papers have citations at least 1
3 3 # there are 3 papers have citations at least 3
2 5 # there are 2 papers have citations at least 5
1 6 # there are 1 paper have citations at least 6# second pointmin(lens - i, count)5 0 -> 0
4 1 -> 1
3 3 -> 3
2 5 -> 2
1 6 -> 1Only when lens - i == count, it will return highest countmin(lens-i, count) can deal with testcase like [100], one paper but with 100 citations, this should return 1
The code:
class Solution:
def hIndex(self, citations: List[int]) -> int:
h = 0
lens = len(citations)
for i, count in enumerate(sorted(citations)):
# lens-i： means how many papers of h importance
# count: means h importance
# min(lens - i, count):
# there are at least (lens-i) papers
# have (lens-i) importance
h = max(h, min(lens - i, count))
return h# ✔ 82/82 cases passed (40 ms)
# ✔ Your runtime beats 59.67 % of python3 submissions
# ✔ Your memory usage beats 5.88 % of python3 submissions (13.3 MB
Solution 2: sort then iterate
class Solution:
def hIndex(self, citations: List[int]) -> int:
citations.sort(reverse=True)
# example: [6, 5, 3, 1, 0] i = 0
while i < len(citations) and citations[i] >= i + 1:
# when stop: citations[2] >= 3
# i + 1 is the number of paper have at least i+1 citations
# i will stop at the maximum
i += 1 # i = 3
return i# ✔ 82/82 cases passed (36 ms)
# ✔ Your runtime beats 97.39 % of python3 submissions
# ✔ Your memory usage beats 5.88 % of python3 submissions (13.3 MB)
