首页 > 代码库 > 未分类随笔
未分类随笔
H-Index
https://leetcode.com/problems/h-index/
这个题还是有些绕的，主要是题意搞得有点晕了。最后题意应该是：h 为 h篇文章的引用至少为h，其余N-h篇文章的引用至多为h。（另外一种错误的理解是引用大于h的至少h篇）
方法一：hashtable
新建一个数组来存储每个引用分别有多少篇文章，由于h最多为文章总数len，所以对于那些引用大于文章总数len的，就把这些文章也加载引用为len次的元素位置。然后从这个数组末尾开始遍历。
使用一个tmp来存储文章数目，遍历到cur，首先更新tmp，表示引用大于等于cur的文章共有tmp篇。如果tmp>=cur,则可以返回cur.
1 class Solution(object): 2 def hIndex(self, citations): 3 """ 4 :type citations: List[int] 5 :rtype: int 6 """ 7 if not citations: 8 return 0 9 length = len(citations)10 articleNum = [0]*(length + 1)11 for i in range(length):12 if citations[i] >= length:13 articleNum[length] += 114 else:15 articleNum[citations[i]] += 116 tmp = 017 for i in range(length, -1, -1):18 tmp += articleNum[i]19 if tmp >= i:20 return i21 return 0
方法二：sort
首先对数组排序，引用次数越多的排在越后边，然后从后边开始遍历。使用tmp表示文章数量，遍历时，如果tmp<citation[i]，tmp++，如果tmp==citation[i]表示有m篇引用至少为tmp,返回tmp即可，如果tmp>citations,[0 1 1 5 6 ]返回tmp-1，因为当前位置不行，下一位置可以。
1 class Solution(object): 2 def hIndex(self, citations): 3 """ 4 :type citations: List[int] 5 :rtype: int 6 """ 7 citations.sort() 8 length = len(citations) 9 tmp = 110 for i in range(length - 1, -1, -1):11 if tmp > citations[i]:12 return tmp - 113 elif citations[i] == tmp:14 return tmp15 else:16 tmp += 117 return length18
未分类随笔
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。