搜狗站长平台验证不了,wordpress改数据库,中国开发网站的公司,沧州免费网站建设题目链接
给你一个整数数组 citations #xff0c;其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义#xff1a;h 代表“高引用次数” #xff0c;一名科研人员的 h 指数 是指他#xff08;她#x…题目链接
给你一个整数数组 citations 其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义h 代表“高引用次数” 一名科研人员的 h 指数 是指他她至少发表了 h 篇论文并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值h 指数 是其中最大的那个。
n citations.length1 n 50000 citations[i] 1000 关键就是这句“至少发表了 h 篇论文并且每篇论文 至少 被引用 h 次”简单点说就是找出 h 个元素里面每个值都大于等于 h。
方法1
那么我们可以从 0 开始枚举每枚举一个数就遍历一次数组检查其合法性这样时间复杂度就为 O ( M a x ( c i t a t i o n s ) ∗ c i t a t i o n s . l e n g t h ) O(Max(citations) * citations.length) O(Max(citations)∗citations.length)最多执行 5*10^6 次。
/*** param {number[]} citations* return {number}*/var hIndex function (citations) {let k 0;let candidate0;while (k citations.length) {let count 0;for (let i 0; i citations.length; i) {citations[i] k count;if (count k k ! 0) {candidate k;break;}}k;}return candidate;
};在 leetcode 上的运行时间击败率太低。
我们另寻他路。
方法2
将数组进行从大到小的排序往后遍历自增量 i 加上 1 就是当前发表论文的最大数量而当前值 citations[i] 就是其中的最小值只要满足 citations[i]i1就是我们要寻找的最大的 H 指数。
/*** param {number[]} citations* return {number}*/var hIndex function (citations) {citations.sort((a, b) b - a);let h 0;for (let i 0; i citations.length; i){if (citations[i] i 1) {h i1;} else {return h;}}return h;
};sort 排序的算法是该方法的时间复杂度的主要开销其底层实现做了很多优化。
V8引擎中数组的sort源码
源码注释说This file implements a stable, adapative merge sort variant called TimSort.
意思是说它是一个稳定的自适应归并排序称为 TimSort。
