My c++ solution using radix sort in 68ms.I think it takes a little long time, how long have you guys use?


  • 0
    S
    void radix_sort(vector<int> &ivec)
    {
    	if (ivec.size() <= 1)
    		return;
    	int dig(1);
    	int flag(true);
    	vector<int> r(ivec.size());
    	vector<int> c(10, 0);
    	while (1)
    	{
    		for (vector<int> ::iterator iter = ivec.begin(); iter != ivec.end(); ++iter)
    		{
    			if (0 == *iter / dig)
    			{
    				c[0] ++;
    			}
    			else
    			{
    				c[(*iter % (10 * dig) - *iter % dig) / dig]++;
    				flag = false;
    			}
    		}
    		for (vector<int> ::iterator iter = c.begin() + 1; iter != c.end(); ++iter)
    		{
    			*iter += *(iter - 1);
    		}
    		if (flag)
    			return;
    		for (vector<int> ::reverse_iterator riter = ivec.rbegin(); riter != ivec.rend(); ++riter)
    		{
    			r[c[(*riter % (10 * dig) - *riter % dig) / dig] - 1] = *riter;
    			--c[(*riter % (10 * dig) - *riter % dig) / dig];
    		}
    		ivec = r;
    		dig *= 10;
    		c = vector<int>(10, 0);
    		flag = true;
    	}
    }
    int maximumGap(vector<int> &num) {
    	if (num.size() < 2)
    		return 0;
    	radix_sort(num);
    	int max_val = num[1] - num[0];
    	int pre = num[0];
    	for (int a : num)
    	{
    		if (a - pre > max_val)
    			max_val = a - pre;
    		pre = a;
    	}
    	return max_val;
    }

Log in to reply
 

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