Java 1ms O(n) solution using counting sort


  • 3
    R
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n+1];
        for (int i = 0; i < n; i++) {
            if (citations[i] > n) count[n]++;
            else count[citations[i]]++;
        }
        for (int i = n; i > 0; i--) {
            if (count[i] >= i) return i;
            count[i-1] += count[i];
        }
        return 0;
    }

Log in to reply
 

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