274. H-Index
1 | class Solution { |
binary search.
先sort, 然后h的范围是1到citations.length. 我们使用binary search找. 对于mid长度, 从末尾开始expand一个window, 里面的数字必须都比mid大. 如果都满足, 那么左边界左边一个位置必须比mid小或等于(如果有的话). 当都满足, 我们让ans = mid, 然后left = mid + 1 从而去找更大的h. 如果是expand的时候失败了, 此时再比mid大的window也不行. 此时我们就让right = mid - 1. 如果是左边界左边一个比mid大, 那我们继续扩大, 此时让left = mid + 1.
时间复杂度: O(nlogn)
空间复杂度: O(1)
1 | class Solution { |
这个二份查找更好.
我们先sort. 首先h的值可以是1到citations.length(为了方便起见, 把citations.length称为n). 也就是我们要看后多少个元素能满足h-index的要求. 但是有个edge case就是最大的citation是0, 那么此时h是0, 这个case我们要单独处理, 于是我们让ans初始化为0. left从1开始表示h最少囊括1个元素, right是n表示h最多囊括n个元素. 然后mid就是此时我们尝试的从尾往前覆盖的宽度. 如果发现这个区间最左边的值大于等于区间宽度, 那么这个区间可能是答案(要么这就是答案, 要么还能接着扩张区间宽度), 于是我们记下此时的宽度到ans中, 至少ans不是0. 然后让left = mid + 1, 即扩大区间的宽度. 如果区间最左边值小于区间宽度, 说明此时这个区间不满足题意, 我们要缩小区间, 于是让right = mid - 1. 如果我们此时还扩大区间, 那不仅得到的区间最左端是减小的趋势, 区间宽度在增加, 因此也一定不满足. 这即是我们用binary search的依据.
时间复杂度: O(nlogn)
空间复杂度: O(logn) 因为sort.