526互联

275.H指数II

发布时间 2023-11-01 15:02:54作者: DawnTraveler

1.题目介绍

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。
请你设计并实现对数时间复杂度的算法解决此问题。

2.题解

2.1 模拟

思路分析

这里使用

代码

class Solution {
public:
  int hIndex(vector<int>& citations) {
​    int h = 0;
​    for (int i = citations.size() - 1; i>=0; i--){
​      if (citations[i] > h) h++; //这里要考虑到我加入一篇新论文之后，比较的论文总数是h+1而不是h, 
​      else return h;
​    }
​    return h; // 若是所有的论文引用次数，都大于n便移动到此处
  }
};

复杂度分析

  • 时间复杂度：O(n) 这里并不满足题目要求！所以我们考虑二分查找思路

2.2 二分查找

思路分析

这里数组已经按升序排列，题目要求要用对数时间复杂度，所以我们就可以直接针对数组进行二分查找。

但是注意这里比较容易错的是，这里是升序排列，所以我们计算已经加入的论文数目时，并不是使用 mid（当前下标） + 1 来计算， 而是使用 len - mid 来进行计算。

原理：比如像结尾：return len - left;
我们使用len - left = 尾下标 + 1 - left；
根据种树原理，尾指针-起始指针+1 = 个数。
也就是说：尾下标 - left + 1 就是我们需要的论文个数

同理 if (citations[mid] >= len - mid) 中使用 len - mid计算已经加入的论文个数
（这里的mid是下标，len是总数目，二者相减计算的刚好是相差的数目）

代码

class Solution {
public:
    int hIndex(std::vector<int>& citations) {
        int len = citations.size();
        int left = 0, right = len;
        while (left < right){
            int mid = left + (right - left) / 2;
            //确保在计算 mid 时不会发生溢出,实际计算和（right+left）/2等效
            if (citations[mid] >= len - mid) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return len - left;
    }
};