[Leetcode] Sort, Hash -- 274. H-Index
2024-10-15 00:56:18
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 has 5
papers in total and each of them had received 3, 0, 6, 1, 5
citations respectively. Since the researcher has 3
papers with at least 3
citations each and the remaining two with no more than 3
citations each, his h-index is 3
.
Solution:
- My idea is to sort the array in descending order; find the index c[i] < i+ 1
iterate to compare the index and value
if the value < index i+1, then stop and return the index as the final answer
if value == index i, return the index i+1
else it is the length of the array
if len(citations) == 0 or citations is None:
return 0
citations = sorted(citations, reverse=True)
#print ('cita: ', citations)
for i, c in enumerate(citations):
if i+1 > c:
return i
elif i+1 == c:
return i+1
return len(citations)
time complexity: o(nlogn), space complexity o(1)
2 nd method is use hashmap
time complexity o(n), space complexity o(n)
get the array value count, when the value > len(array) L, count into the hashmap[L]
--reference
http://www.cnblogs.com/yrbbest/p/5031910.html
if len(citations) == 0 or citations is None:
return 0
dicCount = {}
for ci in citations:
if ci > len(citations):
if len(citations) not in dicCount:
dicCount[len(citations)] = 1
else:
dicCount[len(citations)] += 1
else:
if ci not in dicCount:
dicCount[ci] = 1
else:
dicCount[ci] += 1
#print (' dicCount : ', dicCount)
sum = 0
for i in range(len(citations), -1, -1):
if i in dicCount:
sum += dicCount[i]
if sum >= i:
return i
最新文章
- WebDriver--操控浏览器
- hdu 2897 巴什博弈变形 ***
- 前端开发面试题JS
- 3种用组策略将域帐号加入本地管理员组的方法_jinifly_新浪博客
- 文件转换神器Pandoc使用
- POJ C程序设计进阶 编程题#3 : 排队游戏
- JsonHelper类(序列化和反序列化辅助类)
- [转]LINQ操作数据库
- 【贪心】Codeforces 704B &; 705D Ant Man
- 发生了Post错误:错误代码40005,微信返回错误信息:invalid file type
- jQuery EasyUI的使用入门
- vue enter事件无效,加入native
- js的一些function
- Masonry 与 frame 混用导致的问题
- 系统更新报错--NO_PUBKEY
- Scoop Windows 的命令行安装程序管理工具
- Discrete Log Algorithms :Baby-step giant-step 【二】
- iOS-CoreLocation简单介绍(转载)
- bootstrap3中关于布局的两种样式
- Pku3673
热门文章
- [KISSY5系列]KISSY5安装使用(一)
- log4j的Appenders配置
- JavaScript中var变量引用function与直接声明function
- cmd 命令行模式操作数据库 添加查询 修改 删除 ( 表 字段 数据)
- poj 1001 分析
- NancyFx 2.0的开源框架的使用-Basic
- ionic之$ionicHistory
- win彩 百款皮肤任选任换.可视化
- Asp.Net Core 中获取应用程序物理路径(Getting the Web Root Path and the Content Root Path in ASP.NET Core)
- 习惯的PHP命名规则