My C++ solution, who can simplify?


  • 0
    A

    I think it is too complicated. Where can be simplify and why?

    class Solution {
        public:
            string largestNumber(vector<int> &num) {
                int len =  num.size();
            	string ret;
            	vector<string> strNum;
            	for( int i = 0; i < len; i++ )
            		strNum.push_back( int2str(num[i]) );
            	
            	sort(strNum.begin(), strNum.end(), greatThan);
            	
            	for( int i = 0; i < len; i++ )
            	{
            		if( strNum[i] == "0" && ret == "" )
            			continue;
            		ret += strNum[i];
            	}
            	if( len > 0 && ret == "" )
            		ret = "0";
            	return ret;
            }
        private:
            string int2str( int n )
            {
            	string ret;
            	if( n == 0 )
        		    ret.push_back('0');
            	while( n )
            	{
            		ret.push_back( n%10 + '0' );
            		n /= 10;
            	}
            	reverse( ret.begin(), ret.end() );
            	return ret;
            }
            
            static bool greatThan( string s1, string s2 )
            {
            	int len1 = s1.length(), len2 = s2.length();
            	if( len1 == len2 )
            		return s1 > s2;
            	else if( len1 < len2 )
            	{
            		if( s1 == s2.substr( 0, len1 ) )
            			return greatThan(s1, s2.substr(len1));
            		else
            			return s1 > s2.substr( 0, len1 );
            	}
            	else
            	{
            		if( s2 == s1.substr( 0, len2 ) )
            			return greatThan(s1.substr(len2), s2);
            		else
            			return s1.substr( 0, len2 ) > s2;
            	}
            	return false;
            }
        };

  • 2
    B

    Dear yike,

    You can replace your compare function to return (s1 + s2) > (s2 + s1); And also your int2str can be replaced by using stringsteam. I have made your codes as follows.

    class Solution {
        public:
            string largestNumber(vector<int> &num) {
                int len =  num.size();
                
                vector<string> strNum;
                for( int i = 0; i < len; i++ )
                {
                    stringstream ret;
                    ret << num[i];
                    strNum.push_back(ret.str());
                }
                
                sort(strNum.begin(), strNum.end(), greatThan);
    
                stringstream ret;
                for( int i = 0; i < len; i++ )
                {
                    if( strNum[i] == "0" && ret.str() == "" )
                        continue;
                    ret << strNum[i];
                }
                if( len > 0 && ret.str() == "" )
                     ret << "0";
                return ret.str();
            }
        private:
            static bool greatThan( string s1, string s2 )
            {
                return (s1 + s2) > (s2 + s1);
            }
        };
    

    However, it becomes slower.

    My codes is as follows. For your reference.

    class Solution {
    public:
        static bool compare(int x, int y)
        {
            stringstream s1, s2;
            s1 << x << y; s2 << y << x;
            return s1.str() > s2.str();
        }
        string largestNumber(vector<int> &num) {
            // all zeros
            int k = 0;
            while (!num[k] && k < num.size()) k++;
            if (k == num.size()) return "0";
            
            sort(num.begin(), num.end(), compare);
            
            // not all zeros
            stringstream s;
            for (int i = 0; i < num.size(); i++) s << num[i];
            return s.str();
        }
    };
    

    It's very neat. However it takes 37ms. Anyone knows why it is slow?


  • 2
    P
    class Solution {
    public:
        string largestNumber(vector<int> &num) {
        	vector<string> strings;
        	for(auto dec:num)
        		strings.push_back(to_string(dec));
        
        	sort(strings.begin(), strings.end(), [](string a, string b) {
        		return (b+a) < (a+b);
        	});
        	
        	string maxStr;
        	int i = 0;
        	while(i < strings.size() && strings[i] == "0")
        	    i++;
        	    
        	while(i < strings.size())
        		maxStr += strings[i++];
        
            if (maxStr.size())
        	    return maxStr;
        	else
        	    return "0";
        }
    };
    

    Use lamba to compare, and std::string to convert; It takes 13ms.


  • 0
    Y

    Use to_string instead of stringstream makes it faster


  • 0
    A

    i agree with you


Log in to reply
 

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