O(n) time C++ solution using hash table


  • 21
    I

    class Solution {
    public:

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

    };


  • -7
    K
    	if (citations.size() == 0) return 0;
    	sort(citations.begin(), citations.end());
    	reverse(citations.begin(), citations.end());
    	int hi = 0;
    	int i = 1;
    	while (i - 1 < citations.size() && citations[i-1] >= i) {
    		hi = i;
    		i++;
    	}
    	return hi;

  • 0
    C

    I run your code,but get a error “Line 20: control reaches end of non-void function [-Werror=return-type]”,can you help me?Does anyone meet the same problem?


  • 0
    P

    @cheffyu This is because he is returning i inside a loop. Compiler thinks that it is possible that the control will skip the loop and then see the closing brackets and reach the end without a return function. Simply return i outside the for loop and problem will be solved


Log in to reply
 

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