Easy to understand O(n) time and O(n) space solution


  • 0
    W

    Get the max citation and count each citations number then reverse iterate cumulate the number of citation

    public int hIndex(int[] citations) {
        int max = 0;
        for (int i = 0; i < citations.length; i++) {
            if (citations[i] > max) {
                max = citations[i];
            }
        }
        int[] cit = new int[max + 1];
        for (int i = 0; i < citations.length; i++) {
            cit[citations[i]]++;
        }
        int res = 0;
        for (int i = cit.length - 1; i > 0; i--) {
            res += cit[i];
            if (res >= i) {
                res = i;
                break;
            }
        }
        return res;
    }

  • 2

    This is not O(n). Let m be the maximum element of citations. Suppose m=2^n. You now have an exponential runtime.

    If your algorithm actually ran in linear time, you would've made one of the biggest breakthroughs in computer science. We would now be able to sort any arbitrary list of integers using bucket sort in linear time.


Log in to reply
 

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