17ms custom comparator in c++


  • 0
    C
    string largestNumber(vector<int> &num) {
    	struct {
    		bool operator()(const int &a, const int &b) {
    			string sa = to_string(a), sb = to_string(b);
    			return lessThan(sa, sb);
    		}
    	} comp;
    	sort(num.begin(), num.end(), comp);
    
    	string ret = "";
    	bool firstZero = true;
    	for (int i = num.size() - 1; i >= 0; i--) {
    		if (firstZero && num[i] == 0) {
    			continue;
    		}
    		firstZero = false;
    		ret += to_string(num[i]);
    	}
    	return ret == "" ? "0" : ret;
    }
    

    The algorithm part is as below. It seems this comparison is a bit faster than comparing a + b < b + a. :D

    static bool lessThan(string &a, string &b) {
    	while (true) {
    		size_t alen = a.length(),
    			blen = b.length();
    
    		for (int i = 0; i < min(alen, blen); i++) {
    			if (a[i] < b[i]) {
    				return true;
    			}
    			else if (a[i] > b[i]) {
    				return false;
    			}
    		}
    		if (alen == blen) {
    			return false;
    		}
    
    		if (alen > blen) {
    			a = a.substr(blen);
    		}
    		else {
    			b = b.substr(alen);
    		}
    	}
    }

Log in to reply
 

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