O(n) 1ms solution with extra space


  • 3
    O

    This solution is inspired by skoy12 (https://leetcode.com/discuss/105676/o-n-with-java-1-ms). One modification is that the h-index can be at most n, the length of array. So I change
    "sum = Math.max(i, sum - hindex[i]); " into just "return i".

    public int hIndex(int[] citations) {
    int n = citations.length;
    if (n == 0) return 0;
    int[] hindex = new int[n + 1];
    for(int val: citations){
        if(val >= n) hindex[n]++;
        else hindex[val]++;
    }
    int sum = 0;
    int i = n;
    while (i > 0) {
        sum += hindex[i];
        if (i <= sum) return i;
        i--;
    }
    return 0;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.