[LeetCode August Challange]Day11-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.”

Example:

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.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

---

solution

Time complexity : O(n)
Space complexity : O(n)

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int size = citations.size();
        vector<int> citeCnt(size+1, 0);

        for (int cite: citations) {
            cite = min(cite, size);
            ++citeCnt[cite];
        }
        
        for (int i=size, acc=0; 0<=i; --i) {
            acc += citeCnt[i];
            if (acc>=i) return i;
        }
        
        return size;
    }
};

首先創造容器，記錄cite數量為i的paper有幾篇。(大於總paper數的以總paper數記錄)

以 [3, 0, 6, 1, 5] 為例：

記錄為  0  1  2  3  4  5
       [1, 1, 0, 1, 0, 2]
cite 為 0 的有 1 篇
cite 為 1 的有 1 篇
cite 為 3 的有 1 篇
cite 為 5(或以上) 的有 2 篇

再由高至低，一一累加做比較：

cite數 5 以上的 paper 有 2 篇
cite數 4 以上的 paper 有 2 篇
cite數 3 以上的 paper 有 3 篇 ← 達到 h-index 條件
...