Thursday, January 15, 2015

[Leetcode] Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
Analysis:
An intuitive way to solve the problem is to sort the numbers by some order and then combine the numbers together by descending order.
The question is how should we sort the number? Apparently, it should not be sorted by the integer value. Given two numbers, how do we know which one is "bigger" in term of the combination results is bigger? It is pretty strait forward, just get the two string combinations and compare which one is bigger. For example, [12, 121], since 12121 is greater than 12112, 12121 is the number we want.
The code is pretty strait forward except don't forget to handle the special case of [0, 0], the result should be "0"  rather then "00" as there is no number of "00". 



    static int myComp(int num1, int num2)
    {
        string s1 = to_string(num1) + to_string(num2);
        string s2 = to_string(num2) + to_string(num1);
        return s1 < s2;
    }

    string largestNumber(vector &num) {
        sort(num.begin(), num.end(), myComp);
        //for case [0, 0], if max is 0, then return "0" rather than "00"
        if (num[num.size()-1] == 0)
            return "0";
        string s;
        for(int i=num.size()-1; i>=0; i--)
            s.append(to_string(num[i]));
            
        return s;
    }

No comments:

Post a Comment