274. H-Index

Version #1 Bucket sort

See comments
100.00 %
class Solution {
    public int hIndex(int[] citations) {
        if (citations == null || citations.length == 0) return 0;
        int len = citations.length;
        int[] count = new int[len + 1];
        // count[i] -> number of parpers with citations equals to i
        // e.g. i  0  1  2  3  4
        //         1  1     1
        // if (i == len) -> we must have all papers citation larger than or equals to i
        // say we have 5 numbers and they are 6 7 8 9 10
        // since h index cannot exceed len, we can just put all number larger than len into len
        for (int citation : citations) {
            if (citation >= len) {
                count[len]++;
            } else {
                count[citation]++;
            }
        }
        int sum = 0;
        for (int i = len; i >= 0; i--) {
            sum += count[i]; // there are sum parpers whose citations larger than or equals to i
            if (sum >= i) {
                return i;
            }
        }
        return 0;
    }
}