8ms string based simple solution with explanation


  • 0
    T
    /*
    Main idea: sort the input so that a sequential concatentation will provide the largest number.
    Comparison approximately follows the string comparison (from higher digit to lower digit).
    The only exception is like "12" and "12X" (X can be any number of any non-zero length).
    String comparison regards "12X" as larger because '\0' is smaller then any number charactor, but in this problem only when X is "larger" than "12", "12X" can be considered larger then "12".
    That is because "12X12" is larger than "1212X" only when "X12" is larger "12X".
    Optimization:
    Comparing "X12" and "12X" is equivalent to comparing "X" and "12".
    Because when X<12 or X>12 (this < and > are the comparison for this problem), "X12" < "12X" or > correspondingly.
    And when X=12 (in this problem "1212"="12"), "X12"="12X".
    */
    class Solution {
        //return whether lth is larger than rth
        static bool cmp(const string& lth,const string& rth){
    		//CASE 1, normal string comparison
    		if(lth.size()==rth.size())
    		    return lth.compare(rth)>0;
    		int res=0;
    		size_t min_size=min(lth.size(),rth.size());
    		if(lth.size()<rth.size())
        		res=-rth.compare(0,min_size,lth);
    		else
        		res=lth.compare(0,min_size,rth);
        	if(res!=0)
        	    return res>0;
    		//CASE 2, rear comparison
    		if(lth.size()>rth.size()){
    			return cmp(lth.substr(min_size),rth);
    		}else{
    			return cmp(lth,rth.substr(min_size));
    		}
    	}
    public:
        string largestNumber(vector<int> &num) {
    		vector<string> arr;
    		arr.reserve(num.size());
    		for(int v:num){
    			//arr.push_back(to_string(v));//for speed
        		char temp[30];
        		sprintf(temp,"%d",v);
        		arr.push_back(temp);
    		}
            sort(arr.begin(),arr.end(),cmp);
    		if(arr.empty() || arr[0]=="0")
    			return "0";
    		string res;
    		res.reserve(num.size()*arr[0].size()*2);
    		for(string& v:arr)
    			res+=move(v);
    		return res;
        }
    };

Log in to reply
 

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