C++ solution, "sort first" and "hash table"


  • 3

    sort first

    static bool myfun(int a, int b)
    {
    	return a > b; 
    }
    int hIndex(vector<int>& cit) 
    {
    	if (!cit.size())
    		return 0;
    	int sz = cit.size();
    	sort(cit.begin(), cit.end(), myfun);
    	int i;
    	for (i = 0; i < sz && (cit[i] >= i + 1); ++i);
    	return i;
    }
    

    hash table

    int hIndex(vector<int>& cit)
    {
    	if (!cit.size())
    		return 0;
    	int sz = cit.size();
    	vector<int> table(sz + 1);
    	int i, sum = 0;
    	for (i = 0; i < sz; ++i)
    	{
    		if (cit[i] >= sz)
    			++table[sz];
    		else
    			++table[cit[i]];
    	}
    	for (i = sz; i >= 0; --i)
    	{
    		sum += table[i];
    		if (sum >= i)
    			break;
    	}
    	return i;
    }

Log in to reply
 

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