C++ solution (two different compare functions)


  • 0
    M

    The first one is the same as the previous post. The idea is to really convert the two numbers to their combined form. For example, a=121, b=12, then in the compare function we create two integers 12112 and 12121. Then compare these two integers. Because you create larger numbers from the original, you need to watch out if there is overflow. In addition to the overflow cases, you also need to consider the corner case when the two numbers contain a zero or two.

    bool compare(long long a, long long b) {
        long long k1 = 10;
        while(k1 <= a) k1*=10;
        long long k2 = 10;
        while(k2 <= b) k2*=10;
        return a*k2+b > b*k1+a;
    

    }

    string largestNumber(vector<int> &num) {
        string result;
        if(num.empty()) return result;
        std::sort(num.begin(), num.end(), compare);
        if(num[0]==0) return "0";
        for(auto n:num) 
            result += std::to_string(n);
        return result;
    }
    

    The other compare function simply compares two numbers digit by digit. So there is no overflow case to consider. However, it takes longer time than the previous method. For example, a=121, b=12, we compare each digit of a and b until one runs out of digit. 1==1, 2==2, then b runs out of digits. Then we connect a to the end of b. That is, compare a=1, b=121. We have 1==1 and a runs out of digits. Then we connect b to a. Now, a=12, b=21.

    bool compare(int a, int b) {
    if(a == b) return false;
    
    int k1=1, k2=1;
    while(k1 <= a) k1*=10;
    while(k2 <= b) k2*=10;
    if(a!=0) k1/=10; 
    if(b!=0) k2/=10;
    
    int aa=a, bb=b, kk1=k1, kk2=k2;
    while(kk1>=1 || kk2>=1) {
        int valA = aa/kk1;
        int valB = bb/kk2;
        if(valA > valB) return true;
        if(valA < valB) return false;
        aa%=kk1; kk1/=10; 
        bb%=kk2; kk2/=10;
        if(kk1==0 && kk2==0) break; 
        if(kk1==0) {aa=b; kk1=k2;}
        if(kk2==0) {bb=a; kk2=k1;}
    }
    return false;
    

    }


  • 0
    D
    This post is deleted!

Log in to reply
 

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