179. Largest Number

2020, Oct 28 2 mins read

1. Description

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

2. Note

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

3. Example

Example 1:
Input: nums = [10,2]
Output: “210”

Example 2:
Input: nums = [3,30,34,5,9]
Output: “9534330”

Example 3:
Input: nums = [1]
Output: “1”

Example 4:
Input: nums = [10]
Output: “10”

4. Constraints

1 <= nums.length <= 100
0 <= nums[i] <= $10^9$

5. Solutions

My Accepted Solution

n = i_nums.size()
Time complexity: O($nlg_2n$)
Space complexity: O(n)

class Solution 
{
public:
    // string largestNumber(vector<int>& nums)
    string largestNumber(const vector<int> &i_nums) 
    {
        // This is a special conditon, all numbers are 0, they can't make up a bigger number
        if(count(i_nums.begin(), i_nums.end(), 0) == i_nums.size()) return string("0");
        
        vector<string> numbers(i_nums.size()); // transform numbers into strings to sort them
        for(int i = 0; i < i_nums.size(); i++)
        {
            numbers[i] = to_string(i_nums[i]);
        }
        
        // when making up a number, the most left char matters most, for example, 899 < 900
        // so we need to compare numbers from left to right
        // when we have numbers with different length, wo should repeat their common part, that's means, the short number,since the long number will follow the short number
        // so its left common part will repeat, for example 56 5623 could make up 565623 and 562356

        sort(numbers.begin(), numbers.end(), // use lamda to sort strings
            [](string left, string right) 
            {
                for(int i = 0, j = 0, count = 0; ; ++i, ++j)
                {
                    i %= left.size();
                    j %= right.size();
                    
                    if(left[i] == right[j])
                    {
                        if(count++ > max(left.size(), right.size())) return true; // handle same number
                        
                        continue;
                    }
                    
                    return left[i] > right[j];
                }
            }
            );
        
        for(int i = 1; i < numbers.size(); ++i)
        {
            numbers[0] += numbers[i];
        }
        
        return numbers.front();
    }
};

5.1 Optimize the Sort Function