Use Count Sort, Easy O(n) C++ Solution


  • 0
    R

    The time complexity of Count Sort is O(n+k), where k is the range of array.
    The idea for count sort is to use a vector size of k to record frequency of of each number then travese the vector to make freq[i]= freq[i]+freq[i-1] then the freq[i]-1 will be the index of sorted array

    In this question, we can know that our k is from 0 to n, where n is the length of array
    For an array with each number > n then the H-index will be n
    and for another array with each number =0 then the H-index will be 0

    The algorithm will be 1 first use count sort and for citations[i]>=n we will record hash[n]++
    2 then from the back of hash, hash[i]=hash[i]+hash[i+1]
    3 find the first hash[i]>=i in hash, i is the H-index

    int hIndex(vector<int>& citations) {
        int len = citations.size();
        vector<int> hash(len+1,0);
        for(int i=0;i<len;i++)
        {
            if(citations[i]>=len) hash[len]++;
            else hash[citations[i]]++;
        }
        for(int i=len-1;i>=0;i--)
        {
            hash[i]+=hash[i+1];
        }
        for(int i=len;i>=0;i--)
        {
            if(hash[i]>=i) return i;
        }
        return 0;
    }

  • 0
    R

    Facebook phone interview has a very similar question.
    Given一个unsorted array, find the greatest natural number N, such that, there exists at least N numbers in the array which are greater or equal to N
    The idea is same


Log in to reply
 

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