LeetCode-274 H-Index

题目描述

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

题目大意

给定一个正整数数组，找到数组中的h-index。

（h-index定义为：数组的h-index为数组中的h个数字至少大于等于h，剩余的n-h个数字小于等于h，要求找到其中的最大的h）

示例

Input: citations = [3,0,6,1,5]
Output: 3 
Explanation: [3,0,6,1,5] means the researcher has 5 papers in total and each of them had 
             received 3, 0, 6, 1, 5 citations respectively. 
             Since the researcher has 3 papers with at least 3 citations each and the remaining 
             two with no more than 3 citations each, her h-index is 3.

解题思路

先将数组按从大到小进行排序，然后依次遍历数组，若遇到当前的数字大于等于生于数字个数的时候，返回剩余的数字的个数。若不存在符合条件的数字，则返回0 。

复杂度分析

时间复杂度：O(Nlog(N))

空间复杂度：O(1)

代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        // 数组排序
        sort(citations.begin(), citations.end());
        // 遍历数组，查找符合条件的数字
        for(int i = 0; i < n; ++i) {
            if(citations[i] >= n - i)
               return n - i;
        }
        // 若不存在，返回0
        return 0;
    }
};