9 ms c++ solution with explaination


  • 0
    P
    /*
    LOGIC : sort the numbers based upon the order that which number in the order if kept first would give a higher number
    Case 1: both numbers have same exponent, ex : 12,23 , in this case 23 should come first
    Case 2: a is of higher order than b, ex : 124,23, then make two numbers 12423 and 23124, compare the twon numbers and return true if number 
    generated by a being first gives a higher number
    Case 3 : b is of higher order than a, ex : 23,124 , repeat the case 2
    NOTE : We can improve the efficiency by calculating the exponents before sorting in a hash map
    */
    class Solution {
    public:
    static bool comp (const int& a, const int& b) {
        int temp = a;
        int exp_a = 0;
        while(temp) {
            temp = temp/10;
            exp_a++;
        }
    
        temp = b;
        int exp_b = 0;
        while(temp) {
            temp = temp/10;
            exp_b++;
        }
    
        if (exp_a == exp_b || a == 0 || b == 0) {
           return a > b;
        } else if (exp_a >= exp_b) {
            long num1 = b*pow(10,exp_a) + a;
            long num2 = a*pow(10,exp_b) + b;
            return num2 > num1;
        } else if (exp_b > exp_a) {
            long num1 = a*pow(10,exp_b) + b;
            long num2 = b*pow(10,exp_a) + a;
            return num1 > num2;
        }
    }
        string largestNumber(vector<int> &num) {
            string res = "";
            int n = num.size();
            std::sort(num.begin(), num.end(), comp);
            if (num[0] == 0) {
                return "0";
            }
            for (int i = 0; i < n; ++i) {
                ostringstream os;
                os << num[i];
                res += os.str();
            }
            return res;
        }
    };

  • 0
    L

    I convert the vector of ints to strings from the beginning, it's simple when making the concat. it seems not really necessary to remain the int type to the end I think..


  • 0
    P
    bool comp(const int& a, const int& b) {
        if (a==0) return false;
        if (b==0) return true;
        int e1 = 0;
        int e2 = 0;
        while(a >= pow(10,e1)) e1++;
        while(b >= pow(10,e2)) e2++;
        
        if (e1==e2) return a > b;
        
        long ta = a*pow(10,e2) + b;
        long tb = b*pow(10,e1) + a;
        return ta > tb;
    }
    class Solution {
    public:
        string largestNumber(vector<int> &a) {
           int n = a.size();
           if (n==0) return "0";
           string res = "";
           std::sort(a.begin(), a.end(), comp);
           if (a[0]==0) return "0";
           int i = 0;
           while(i < n) {
               res += std::to_string(a[i]);
               i++;
           }
           return res;
        }
    };

  • 0
    P

    Simplified my previous solution


Log in to reply
 

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