LeetCode 275. H-Index II

275. H-Index II

Description Submission Solutions

Total Accepted: 42241
Total Submissions: 125172
Difficulty: Medium
Contributors: Admin

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

Hint:

Expected runtime complexity is in O(log n) and the input is sorted.

Subscribe to see which companies asked this question.

【题目分析】

相比上个题目，这次直接给定了一个有序的序列。要求以O(logn)的时间复杂度返回结果。

【思路】

对于一个有序的序列，我们自然想到的就是二分查找算法。如何来做呢？我们画图分析一下：

1. 上图是一个递增的序列，下面一行是此处若满足条件对应的h值。可见h值是降序序列。因此在二分查找的过程中，如果某个h值满足条件（即h值小于它对应的值），我们就到前半部分继续查找；如果h值不满足条件（即h值大于它对应的值），我们就到前半部分继续查找。

2. 对于一些边界情况，如果在最左边查找成功或者失败，则此时left=0，h=len（即len-left）；如果在最右边查找失败，left会溢出，left=len，此时h=len-left=0.

【java代码】

 1 public class Solution {
 2     public int hIndex(int[] citations) {
 3         int len = citations.length;
 4         
 5         int left = 0, right = len-1;
 6         while(left <= right) {
 7             int mid = left+(right-left)/2;
 8             if(citations[mid] >= len-mid) right = mid - 1;
 9             else left = mid + 1;
10         }
11         return len - left;
12     }
13 }