H - Index
人这一生能有多少痛苦？能做错多少选择？我好痛苦。我本不该如此的。
274. H-Index
计算h - index：”A scientist has index h if hof his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
我觉得可以先排序然后找到最后一个i，length - i >= citations[i]. O(NlgN), O(1).
class Solution {
public int hIndex(int[] citations) {
if(citations == null || citations.length == 0) {
return 0;
}
Arrays.sort(citations);
int l = 0, r = citations.length - 1, res = 0;
while(l < r) {
int mid = l + (r - l)/2;
if(citations[mid] < citations.length - mid) {
l = mid + 1;
} else {
r = mid;
}
}
if(citations[l] < citations.length - l) return 0;
return citations.length - l;
}
}
当时没有想到Bucket sort的方法，只需要O(N).
public class Solution {
public int hIndex(int[] citations) {
// bucket sort O(n)
int length = citations.length;
if(length == 0) return 0;
int[] buck = new int[length+1];
for(int i: citations) {
if(i >= length) {
buck[length]++;
}else{
buck[i]++;
}
}
int count = 0;
for(int i = length; i >= 0; i--){
count += buck[i];
if(count >= i) {
return i;
}
} // for i
return 0;
}
}
275. H-Index II
把274排序了。lg(N)
class Solution {
public int hIndex(int[] citations) {
if(citations == null || citations.length == 0) {
return 0;
}
int l = 0, r = citations.length, res = 0;
while(l < r) {
int mid = l + (r - l)/2;
if(citations[mid] < citations.length - mid) {
l = mid + 1;
} else {
r = mid;
}
}
return citations.length - l;
}
}
我真的忍无可忍啊。这工作为什么会这样？能不好的地方都不好。我到底什么时候能解脱？