首页 > itarticle > leetcode:h-index ii

leetcode:h-index ii

admin 11月 11, 2020 0

一、题目要求

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

二、分析

若引用次数数组已经增序排列，如何优化算法？时间开销要求$O(log n)$

三、思路

1.二分查找即可

时间开销:$O(log n)$,空间开销:$O(1)$,结果:AC

L, R ,length = 0, len(citations) - 1,len(citations)

while L <= R:
    mid = L + R >> 1
    if length - mid > citations[mid]:
        L = mid + 1
    elif length - mid < citations[mid]:
        R = mid - 1
    else:
        return citations[mid]

return length - L