赞
踩
H指数,通俗来讲,将其转化为数组值与数组大小的关系。拿第一个案例[3, 0, 6, 1, 5]来看,从符合条件的元素个数入手,假设h=1,此时h指数为1,意思是该数组内有一个数大于等于1,该假设成立;那么当h=2时,意思是该数组内有一个数大于等于2,很明显该假设也成立,但第一个h=1,第二个h=2,题目明确说取最大值,那么就舍弃掉第一个h,此时h=2;继续,当h=3时,数组内有三个数大于等于3,毫无疑问,该假设也是成立的,那么本轮得到的h=3,同理,舍弃较小值,此时h=3;而假设当h=4时,意为给定数组中有4个元素的值大于等于4,那么事实上大于4的只有5和6两个元素不符合当前h=4的条件,因此该假设不成立;同理当4不满足时就没有必要往后假设了,因为只会有更少的元素值大于等于5及以上。以上就是我们初步的模拟思路。那么进入解题阶段,多样例多元素总不能一直假设,那么尝试让元素跳过假设,也就是说在数组中越大的元素越容易被满足,至于比它小的数再判断即可。那么首先将数组sort排序,得到一个非递减序列,从后往前遍历,如果遍历到的数值大于h则说明该元素符合条件,此时h增1。
- class Solution {
- public:
- int hIndex(vector<int>& citations) {
- sort(citations.begin(), citations.end());
- // [0, 1, 3, 5, 6]
- int n = citations.size();
- int i = n - 1;
- int h = 0; // 最后的h指数
- for (int i = n - 1; i >= 0; --i) {// 本轮符合条件的个数
- if (citations[i] > h) {
- h++;
- }
- }
- return h;
- }
- };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。