leetcode Question: Largest Number

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:

The key to this question is  ---- Don't think it too complicated.
No recursion, no DP, no complicated sorting is needed.

Let's look at the question in this way:
(1) All the numbers are used. (No need to choose)
(2) Order of the numbers is important. (May use sorting algorithm)
(3) How to determine the order of  like 30 and 3?   3>30? 3< 30?

So it is natural to think that sorting is all we need. If I can get the sorted list of numbers, the last step is just concatenate them and output as a string.

Sort can be done by calling library functions (e.g., c++ sort(a.begin(), a.end(), _comp), python sorted(a, comp)), where we need to define the compare function.  Note that in c++,  _comp in sort function need to be static.  

How to define the compare function?
1. Consider two int, a and b.  e.g., 34 and 3.
2. Actually, what we need to compare is not 34 and 3, but  3 43 and 3 34. 
3. If 343 > 334, then 34 should have higher order than 3, and vice versa.


In my code, the int are converted into string in case of long length. In c++, stringstream is a good way to do so.

Note:
(1) In c++, comp function must be static and it returns true and false.
(2) In python, comp function must return positive , 0 and negative numbers to represent greater, equal and smaller.  (see note 8 in here)
(3) In sort function, ascending order is the default. So in my code I change the order in comp function so that the output is descending order.
(4) String compare, either in C++ or Python, is comparing each char from the start. And if the compared string is shorter, it will return "smaller"

Code(C++):

class Solution {
public:
    static bool _comp(int a, int b){
        ostringstream ss;
        ss << a;
        string sa = ss.str();
        ss.clear();
        ss << b;
        string sb = ss.str();
        ss.clear();
        
        sa = sa + sb;
        sb = sb + sa;
        
        if (sa.compare(sb) >=0){
            return true;
        }else{
            return false;
        }
    }

    string num2str(int i){
        ostringstream ss;
        ss << i;
        return ss.str();
    }
    
    string largestNumber(vector<int> &num) {
        
        string res="";
        
        sort(num.begin(),num.end(), _comp);
        
        if (num[0]==0){return "0";}
        
        for(int i=0;i<num.size();i++){
            res = res+ num2str(num[i]);
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        def my_cmp(x,y):
            sx = str(x)
            sy = str(y)
            sx = sx + sy
            sy = sy + sx
            if sx > sy:
                return -1
            if sx == sy:
                return 0
            if sx < sy:
                return 1
           
        num = sorted(num, cmp=my_cmp)
        
        if num[0] == 0:
            return "0"
        else:
            return "".join([str(n) for n in num])