C++ 7ms solution


  • 0
    P
    static const int DECIMALS[] = {
    		1,
    		10,
    		100,
    		1000,
    		10000,
    		100000,
    		1000000,
    		10000000,
    		100000000,
    		1000000000,
    };
    
    class Solution {
    	static bool compare(int i, int j) {
    		int leni, lenj;
    
    		if (i == 0 && j == 0) {
    			return false;
    		} else if (i == 0) {
    			return false;
    		} else if (j == 0) {
    			return true;
    		}
    
    		if (i == j) {
    			return false;
    		}
    
    		leni = 0;
    		for (int k = 9; k >= 0; --k) {
    			if (i >= DECIMALS[k]) {
    				leni = k + 1;
    				break;
    			}
    		}
    		lenj = 0;
    		for (int k = 9; k >= 0; --k) {
    			if (j >= DECIMALS[k]) {
    				lenj = k + 1;
    				break;
    			}
    		}
    
    		int inv = false;
    		if (leni < lenj) {
    			inv = true;
    			int temp = leni;
    			leni = lenj;
    			lenj = temp;
    
    			temp = i;
    			i = j;
    			j = temp;
    		}
    
    		int diff = leni - lenj;
    		int comp = i / DECIMALS[diff];
    		if (comp > j) {
    			if (inv) {
    				return false;
    			} else {
    				return true;
    			}
    		} else if (comp < j) {
    			if (inv) {
    				return true;
    			} else {
    				return false;
    			}
    		}
    
    		int firsti = i / DECIMALS[lenj];
    		int lasti = i % DECIMALS[diff];
    		if (firsti < lasti) {
    			if (inv) {
    				return false;
    			} else {
    				return true;
    			}
    		} else if (firsti > lasti) {
    			if (inv) {
    				return true;
    			} else {
    				return false;
    			}
    		}
    
    		lasti = i % DECIMALS[lenj];
    		if (inv) {
    			return (j < lasti);
    		} else {
    			return (j > lasti);
    		}
    	}
    
    public:
    	string largestNumber(vector<int> &num) {
    
    		sort(num.begin(), num.end(), compare);
    		if (num[0] == 0) {
    			return "0";
    		}
    
    		char strn[11] = { 0 };
    		string result;
    
    		result.reserve(8 * num.size());
    		for (vector<int>::iterator it = num.begin(); it != num.end(); ++it) {
    			sprintf(strn, "%d", *it);
    			result += strn;
    		}
    
    		return result;
    	}
    };

Log in to reply
 

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