本地电脑如何做网站服务器,ml免费域名注册,衡水网站开发,做效果图常用的网站有哪些软件文章目录 Tag题目来源题目解读解题思路方法一#xff1a;二分查找 写在最后 Tag
【二分查找】【数组】【2023-10-30】 题目来源
275. H 指数 II 题目解读
本题与 274. H 指数 题目一致#xff0c;只是加强了一下条件#xff0c;数组是有序的。 解题思路
方法一#xff… 文章目录 Tag题目来源题目解读解题思路方法一二分查找 写在最后 Tag
【二分查找】【数组】【2023-10-30】 题目来源
275. H 指数 II 题目解读
本题与 274. H 指数 题目一致只是加强了一下条件数组是有序的。 解题思路
方法一二分查找
我们二分枚举论文的索引设查找范围的初始左边界 l 为 0, 初始右边界 r 为 n−1其中 n 为数组 citations 的长度。每次在查找范围内取中点 mid则有 n−mid 篇论文被引用了至少 citations[mid] 次
如果在查找过程中满足 citations[mid]≥n−mid则移动右边界 r否则移动左边界 l;
最后返回 n - l。
实现代码
class Solution {
public:int hIndex(vectorint citations) {int n citations.size();int l 0, r n - 1;while (l r) {int mid l ((r - l) 1);if (citations[mid] n - mid) {r mid - 1;}else {l mid 1;}}return n - l;}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn) n n n 为数组 citations 的长度。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
