leetcode：274. H 指数

题目

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
根据维基百科上 h 指数的定义：h 代表“高引用次数”，一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。且其余的 n - h 篇论文每篇被引用次数 不超过 h 次。
如果 h 有多种可能的值，**h** 指数 是其中最大的那个。

示例：

输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

输入：citations = [1,3,1]
输出：1

解答 & 代码

解法一：排序 + 遍历查找

class Solution {
public:
    int hIndex(vector<int>& citations) {
        // 1. 对数组排序（这里用的从小到大排序）
        sort(citations.begin(), citations.end());
        int len = citations.size();
        // 2. 遍历数组，找到第一个满足 citations[i] >= len - i 的下标 i
        // 下标 i 及其之后的数都大于等于 len - i，共 len - i 个数，因此直接返回 len - i
        for(int i = 0; i < len; ++i)
        {
            if(citations[i] >= len - i)
                return len - i;
        }
        return 0;
    }
};

复杂度分析：设数组长为 N

• 时间复杂度 O(N logN)：排序时间复杂度
• 空间复杂度 O(1)：如果算排序的空间复杂度应该是 O(logN)

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 48.34% 的用户
内存消耗：8.5 MB, 在所有 C++ 提交中击败了 21.11% 的用户

解法二：排序 + 二分查找

1. 排序（从小到大排序）
2. 二分找到满足 citations[mid] >= n - mid 的左边界

   class Solution {
   public:
    int hIndex(vector<int>& citations) {
        // 1. 排序（从小到大排序）
        sort(citations.begin(), citations.end());
        int len = citations.size();
        // 2. 二分找到满足 citations[mid] >= n - mid 的左边界
        int left = 0;
        int right = len - 1;
        int leftBoundary = len;
        while(left <= right)
        {
            int mid = left + (right - left) / 2;
            if(citations[mid] >= len - mid)
            {
                leftBoundary = mid;
                right = mid - 1;
            }
            else
                left = mid + 1;
        }
        return len - leftBoundary;
    }
   };
   

   复杂度分析：设数组长为 N

• 时间复杂度 O(N logN)：排序时间复杂度
• 空间复杂度 O(1)：如果算排序的空间复杂度应该是 O(logN)

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 48.34% 的用户
内存消耗：8.4 MB, 在所有 C++ 提交中击败了 34.14% 的用户