企业官网建设流程全解析

做医疗护具网站,广州做网站费用,网站建设p2p,苏州网站制作网站建设题目描述 给你一个整数数组 citations #xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数#xff0c;citations 已经按照 非降序排列 。计算并返回该研究者的 h 指数。 h 指数的定义#xff1a;h 代表“高引用次数”#xff08;high citations#xff…题目描述给你一个整数数组citations其中citations[i]表示研究者的第i篇论文被引用的次数citations已经按照非降序排列。计算并返回该研究者的 h指数。h 指数的定义h 代表“高引用次数”high citations一名科研人员的h指数是指他她的 n篇论文中至少有h篇论文分别被引用了至少h次。请你设计并实现对数时间复杂度的算法解决此问题。示例 1输入citations [0,1,3,5,6]输出3解释给定数组表示研究者总共有 5篇论文每篇论文相应的被引用了 0, 1, 3, 5, 6次。由于研究者有3篇论文每篇至少被引用了 3次其余两篇论文每篇被引用不多于3次所以她的h指数是 3 。示例 2输入citations [1,2,100]输出2提示n citations.length1 n 1050 citations[i] 1000citations按升序排列解决方案算法目标计算科研人员的H指数找到一个最大的整数h使得该科研人员至少有h篇论文的被引用次数至少为h次。核心思路排序论文引用次数便于后续统计二分查找h值在[0, n]范围内查找满足条件的最大h验证条件统计引用次数≥h的论文数量是否≥h算法步骤1. 预处理sort(citations.begin(), citations.end());对引用次数进行排序虽然排序不是必需的但能使二分查找更直观2. 确定查找范围int left -1; // 不可行的下界int right len 1; // 可行的上界开区间h的取值范围[0, n]n为论文总数使用开区间(left, right)保证left不可行right可行3. 二分查找while(left 1 right) { int mid (left right) / 2; // 尝试的h值 int ans 0; // 统计引用次数 ≥ mid 的论文数 for(auto a : citations) { if(a mid) ans; } if(ans mid) { left mid; // mid可行尝试更大的h } else { right mid; // mid不可行尝试更小的h } }4. 返回结果return left; // 最大的可行h值关键点解释循环不变量left最后一个已知可行的h值right第一个已知不可行的h值区间(left, right)为开区间其中可能有可行值判断逻辑如果ans mid有至少mid篇论文被引用至少mid次 → mid可行如果ans mid不满足h指数条件 → mid不可行返回值返回left即最大的可行h值因为right是第一个不可行的h值left是最后一个可行的h值时间复杂度排序O(n log n)二分查找O(log n)次迭代每次迭代统计O(n)总时间O(n log n)空间复杂度O(1) 或 O(n)取决于排序算法示例citations [3,0,6,1,5]排序后: [0,1,3,5,6]二分查找过程尝试 h2: 有3篇≥2 → 可行尝试 h4: 有2篇≥4 → 不可行尝试 h3: 有3篇≥3 → 可行结果: h3算法特点通用性强不依赖特殊数据结构逻辑清晰直接对应H指数定义效率适中适合中等规模数据易于理解二分查找框架清晰函数源码class Solution { public: int hIndex(vectorint citations) { sort(citations.begin(),citations.end()); int len citations.size(); int left0; int rightlen1; while(left1right){ int mid(leftright)/2; int ans0; for(auto a:citations){ if(amid) ans1; } if(ansmid) leftmid; else rightmid; } return left; } };