LeetCode:(Python)(Array)H-index

題目連結: https://leetcode.com/problems/h-index/description/?envType=study-plan-v2&envId=top-interview-150

題意說明:

• 有一個指標叫做 H-index
• H-index是指至少有n篇文章被引用n次的最大值

下圖範例中，至少有1篇文章被引用1次，至少有2篇文章被引用2次，至少有3篇文章被引用3次，取最大值: 3

實作程式碼一

我們可以由小而大的找，從至少有0篇文章被引用0次，往1,2, . . .找。

1. 排序被引用次數，倒序。
2. 找到 i大於等於被引用次數時，就找到
3. 如果都沒有找到，代表被引用次數 >= 發表文章數，回傳發表文章數 (i.e. length)

citation = [3, 0, 6, 1, 5]

倒序: [6, 5, 3 ,1 0]

i : [0, 1, 2, 3, 4]

6>0 -> 5>1 -> 3 >2 -> 1<3

因此答案是3

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

        for i in range(length):
            if i >= citations[i]:
                return i

        return length

實作程式碼二

不排序的做法

citation = [3, 0, 6, 1, 5]

[1,1,0,1,2] (mapping)

[0,1,2,3,4] (i，第幾個數字)

[5,4,3,3,2] (aggreagate)

從 length 往下-1遞減，目標是找到最大的 i

i = 4

aggreagate = 2

i = 3

aggreagate = 3

i = 2

aggreagate = 3

所以答案是3

class Solution:
    def hIndex(self, citations: List[int]) -> int:
        length = len(citations)
        mapping = [0]*(length+1) #用來記錄每一個被引用次數各有幾次

        for c in citations:
            #如果被引用次數大於論文發表數，一律登記為論文發表數
            #因為 H index 的最大值就是論文發表數
            #如果只有發表5篇論文，不可能有6篇文章被引用6次
            if c >= length: 
                mapping[length] = mapping[length] + 1
            else:
                mapping[c] = mapping[c] + 1

        aggragate = 0
        for i in range(length,-1,-1):
            aggragate = aggragate + mapping[i]
            if aggragate >= i:
                return i

        return 0