Medium
Related Topics: Array / Sorting / Counting Sort
LeetCode Source

解題想法

這題我卡在如何處理累積 index 數目，但最後才知道不用算累積

用儲存容器的 index 跟 index 的數目比較就好

首先先把 citations 由大排到小 sort(citations.begin(), citations.end(), greater());

在來比較 i+1 跟 citations[i] 的大小

• 若 i 小於等於 citations[i]，則有這個解
• 反之，則跳出迴圈回傳答案

舉例來說 citations = [3,0,6,1,5]

由大排到小 citations = [6,5,3,1,0]

此時觀察

citations[0] = 6
citations[1] = 5
citations[2] = 3 # at most H-Index is 3
citations[3] = 1
citations[4] = 0

Python

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        res = 0
        citations.sort(reverse=True)

        for i, cite in enumerate(citations, start=1):
            if i <= cite:
                res = i
            else:
                break
        return res

start=1 代表說 i 這個 index 從 1 開始

C++

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater());
        int res = 0;

        for (int i = 0; i < citations.size(); i++) {
            if (i+1 <= citations[i]) 
                res = i+1;
            else
                break;
        }
        return res;
    }
};

這系列文被記錄在 Top Interview 150 Series