一. 題目描述
Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?
二. 題目分析
該題與H-Index一題的要求基本一致，只是多提供了一個條件，即傳入的數組本身已經是升序排列的，因此實際上操作會方便許多，也無需再使用輔助數組。該題仍然可以使用H-Index方法從後往前遍歷數組，即可計算出h指數，算法復雜度為O(n)，但更快的方法是使用二分查找，復雜度降為O(logn)。
三. 示例代碼
// 簡單的從後往前遍歷數組，較為耗時
class Solution {
public:
int hIndex(vector& citations) {
if (citations.size() == 0) return 0;
int result = 0;
for (int i = citations.size() - 1; i >= 0; --i)
{
if (result >= citations[i])
return result;
++result;
}
return citations.size();
}
};
// 二分查找，效率更快
class Solution {
public:
int hIndex(vector& citations) {
int size = citations.size();
if (size == 0)
return 0;
int left = 0, right = size - 1;
while (left < right){
int mid = left + (right - left) / 2;
if (size - mid > citations[mid])
left = mid + 1;
else
right = mid;
}
return (size - right) < citations[right] ? (size - right) : citations[right];
}
};
四. 小結
題目的提示略顯多余。
