My 9ms C++ solution


  • 1
    M

    It's similar to the string-based solutions, except that I just write the digits to an int array to avoid all the string allocations.

    int toArray(int number, int *digitArray)
    {
    	int index = 0;
    	do
    	{
    		digitArray[index] = number % 10;
    		number /= 10;
    		index++;
    	} while (number > 0);
    	return index;
    }
    
    // Max of 10 digits in a 32 bit number, and we're appending two
    int digitWorker[20];
    
    // Returns true if a is less than b
    bool isLessThan(int a, int b)
    {
    	int aLength = toArray(a, digitWorker);
    	int bLength = toArray(b, digitWorker + aLength);
    	int totalLength = aLength + bLength;
    	int compare = 0;
    	for (int i = (totalLength - 1); !compare && (i >= 0); i--)
    	{
    		int bDigit = digitWorker[i];
    		int aDigit = digitWorker[(i + aLength) % totalLength];
    		compare = (aDigit - bDigit);
    	}
    	return compare < 0;
    }
    
    class Solution {
    public:
    	string largestNumber(vector<int> &num) {
    		std::sort(num.begin(), num.end(), isLessThan);
    		if (num.back() == 0)
    		{
    			return "0";
    		}
    		ostringstream result;
    		for (int i = num.size() - 1; i >= 0; i--)
    		{
    			result << num[i];
    		}
    		return result.str();	    
    	}
    
    };

Log in to reply
 

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