一魚多吃 用二分搜尋法 計算h-index_Leetcode #275

這題的題目在這裡

題目敘述

題目給定一個已排序的輸入陣列，陣列裡面的數字自分別代表每篇論文的被引用數。

要求我們計算h-index。

h-index的定義:
找一個最大的h值，使得有h篇論文，個別論文的被引用數都 大於等於 h

這一題算是前一題的類似題，但是多加了一個很強的條件，輸入陣列已排序。

測試範例

Example 1:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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, their h-index is 3.
有三篇論文引用數大於等於3
分別是[3, 5, 6]​

Example 2:

Input: citations = [1,2,100]
Output: 2
有兩篇論文引用數大於等於2
分別是[2, 100]

約束條件

Constraints:

• n == citations.length
• 1 <= n <= 105
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

演算法

除了前一題介紹使用的Counting sort框架的演算法；這題因為多給了一個比較強的條件，輸入陣列已經從小到大排序好。

利用這個性質: 在已經排序好的陣列裡面做搜尋，適合使用二分搜尋法。

因此，就用h-index本身的定義做為目標值的條件判斷，用二分搜尋法去不斷逼近最大的h 值。

再次複習 h-index的定義:
找一個最大的h值，使得有h篇論文，個別論文的被引用數都 大於等於 h

程式碼

class Solution:
　def hIndex(self, citations: List[int]) -> int:
　　
　　left, right = 0, len(citations)-1
　　
　　size = len(citations)
　　
　　while left <= right:
　　　
　　　mid = left + (right - left)//2
　　　
　　　the_number_of_larger_equal_to_current = size - mid
　　　h_index = citations[mid]
　　　
　　　
　　　if h_index < the_number_of_larger_equal_to_current:
　　　　# current h index is too small, make it larger
　　　　left = mid + 1
　　　　　
　　　elif h_index > the_number_of_larger_equal_to_current:
　　　　# current h index is to large, make it smaller
　　　　right = mid - 1
　　　
　　　else:
　　　　# meet the definition of h-index
　　　　return h_index
　　　
　　return size - left 

複雜度分析

時間複雜度:

O( log n ) 使用二分搜尋法去逼近目標值，每次可以排除一半的區間，最多耗費log(n)步可以找到h-index

空間複雜度:

O(1) 只有使用固定的臨時變數，所耗費的記憶體空間為常數級別O(1)

關鍵知識點

想到這個性質: 在已經排序好的陣列裡面做搜尋，適合使用二分搜尋法。

因此，就用h-index本身的定義做為目標值的條件判斷，用二分搜尋法去不斷逼近最大的h 值。

再次複習 h-index的定義:
找一個最大的h值，使得有h篇論文，個別論文的被引用數都 大於等於 h

記得和h-index系列題的第一題做個對照。

Reference:

[1] LeetCode - The World's Leading Online Programming Learning Platform