Lintcode: Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

Have you met this question in a real interview? 

Yes

Example

Given [1, 20, 23, 4, 8], the largest formed number is 8423201.

Note

The result may be very large, so you need to return a string instead of an integer.

Tags Expand 

LintCode Copyright Sort

STL: sort 
String compare

Codes reference: http://leetcodesolution.blogspot.com/2015/01/leetcode-largest-number.html

Thought:
At first, I think of creating 10 sets to store numbers begin with 0 to 9. However, problem is how to sort numbers begin with the same number. We have to judge those numbers by their bit like
35, 351, 34, 33, 3, 32, 323
A simple way is to compare str1+ str2 & str2 + str1. String is able to compare according to ASICII order. Since the digits of two strings are same, the string comparison can be used to directly compare the integer expressed from string.

Time: O(nlogn)   -- quicksort
Space: O(1)

class Solution {
public:
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    static bool mycomp(int a, int b){  //don't forget static
       return to_string(a) + to_string(b) < to_string(b) + to_string(a);
    } 
     
    string largestNumber(vector<int> &num) {
        // write your code here
        sort(num.begin(), num.end(), mycomp);
        if(num[num.size() - 1] == 0) return "0";
        string res;
        for(int i = num.size() - 1; i >= 0; i--){
            res += to_string(num[i]);
        }
        return res;
    }
};

Lintcode second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

class Solution { public: /** *@param num: A list of non negative integers *@return: A string */ static bool cmp(int a, int b){ return to_string(a) + to_string(b) > to_string(b) + to_string(a); } string largestNumber(vector<int> &num) { // write your code here sort(num.begin(), num.end(), cmp); //in case the largest number is zero and then the highest digit of result will be zero if(num[0] == 0) return "0"; string res; for(int i = 0; i < num.size(); i++){ res += to_string(num[i]); } return res; } };