275. H-Index II
Description
Pitfall
很容易想到用binary search来解决这个问题。
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
int left = 0, right = citations.length - 1, len = citations.length;
// h = (left,right) / 2, citations[h] >= nums.length - 1 - h + 1
// last occurrence
while (left < right) {
final int mid = left + (right - left) / 2, h = len - mid;
if (citations[mid] >= h) {
right = mid;
} else {
left = mid + 1;
}
}
return len - left;
}
但这样做会miss mid == nums.length, 对应的就是h指向exclusive的右边界的时候；
如果要发生这种情况发生，就要有 h及h右边有h个论文有至少h个citations，但h指的是最右边exclusive，就是0。 所以
Solution
public int hIndex(int[] citations) {
if (citations == null || citations.length == 0) {
return 0;
}
// 排出上述的特殊情况
if (citations[citations.length - 1] == 0) {
return 0;
}
int left = 0, right = citations.length - 1, len = citations.length;
// h = (left,right) / 2, citations[h] >= nums.length - 1 - h + 1
// last occurrence
while (left < right) {
final int mid = left + (right - left) / 2, h = len - mid;
if (citations[mid] >= h) {
right = mid;
} else {
left = mid + 1;
}
}
return len - left;
}