【刷题-LeetCode】275. H-Index II
2024-09-28 06:40:45
- H-Index II
Given an array of citations sorted in ascending order (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."
Example:
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had
received 0, 1, 3, 5, 6 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, her h-index is 3.
Note:
If there are several possible values for h, the maximum one is taken as the h-index.
Follow up:
- This is a follow up problem to H-Index, where
citations
is now guaranteed to be sorted in ascending order. - Could you solve it in logarithmic time complexity?
解 h-index:和爱丁顿数一个定义。对于一个从小到大排列好的数组,h-index为:
\[h = \arg \max \{nums[n-i] >= i\}
\]
\]
最简单是线性搜索,逐一判断即可。在有序数组中,可以使用二分查找
class Solution {
public:
int hIndex(vector<int>& citations) {
int l = 0, r = citations.size()-1;
while(l <= r){
int mid = (l+r)/2;
if(citations.size()-mid == citations[mid])return citations.size()-mid;
if(citations.size()-mid > citations[mid])l = mid+1;
else r = mid-1;
}
return citations.size()-l;
}
};
最新文章
- [转]使用Jenkins搭建持续集成(CI)环境
- java中观察者模式Observable和Observer
- Qt开发中的实用笔记三--关于各种类的零碎知识点:
- web工具网站等
- cordova
- TCP/IP协议 三次握手与四次挥手
- MVC缓存技术
- 《shell脚本if..then..elif..then.if语句的总结》
- 方形布局SquareLayout
- 【DSA MOOC】起泡排序的原理及常数优化
- HDU 2859 Phalanx
- Linux Shell -- 无网不利
- linux常用命令简述
- leetcode121
- EasyUI tabs update 正确用法
- beamer template
- 在城市后面加上省,市,区 以及将MySQL入库脚本封装成class
- make报错
- Linux文本编辑器快捷方式
- AndroidStudio的一些快捷键的使用
热门文章
- Jaeger知识点补充
- [Elasticsearch] ES 的Mapping 设计在实际场景中应用
- 在react项目中使用require引入图片不生效
- 重学c#系列——datetime 和 datetimeoffset[二十一]
- codeforces 624C Graph and String
- git安装与使用,未完待续... ...
- [zbar]zbar条码扫描器解析示例
- BL8810|USB2.0高速闪存读卡器|BL8810芯片
- 编写Java程序,用户在网上购买商品(good),当用户买了一本书(book)、一顶帽子(hat)或者买了一双鞋子(shoe),卖家就会通过物流将商品邮寄给用户,使用简单工厂模式模拟这一过程。
- Jsonschema2pojo从JSON生成Java类(命令行)