H-Index

https://leetcode.com/problems/h-index/

Bucket sort is really efficient in solving particularly these type of problems: https://discuss.leetcode.com/topic/40765/java-bucket-sort-o-n-solution-with-detail-explanation

Keys: the indices for bucket array are citations themselves.

public int hIndex(int[] citations) {
int len = citations.length;
int[] bucket = new int[len+1];
for(int c : citations){
if(c >= len){
bucket[len]++;
} else {
bucket[c]++;
}
}

int count = 0;
for(int i = len; i >= 0; i--){
count += bucket[i];
if(count >= i) return i;
}
return 0;
}

Bucket sort is really efficient: the above code is O(n), only 1 ms while a naive sorting and then finding is at least O(nlogn) (4ms).

Advertisements