C++ O(n) solution with sort only, no hash table


  • 0
    S

    I don't think hash table is necessary here. Sort the citation array first, then from end of array, bump hIndex by 1 if the current number in array >= distance from current location to the end. After went through the citation array, you will have the hIndex. The complexity is O(n) excluding the sort.

    For example, if we have c = {0,0,4,4} as sorted citation array, from the last element in array:
    4 is >= (c.size() - 3), bump hIndex;
    4 is >= (c.size() - 2), bump hIndex;
    0 is < (c.size() - 1), do nothing;
    0 is < (c.size() - 0), do nothing;
    Then you have a hIndex = 2;

    class Solution {
    public:
        int hIndex(vector<int>& citations) {
            
            sort(citations.begin(), citations.end());
            
            int hIndex = 0;
            for (int i = citations.size() - 1; i>=0; i--) {
                if (citations.size() - i <= citations[i]) hIndex++;
            }
            
            return hIndex;
        }
    };
    

Log in to reply
 

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