largest-number

179. Largest Number

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

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

Example 1:

Input: nums = [10,2] Output: "210"

Example 2:

Input: nums = [3,30,34,5,9] Output: "9534330"

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        int n = nums.size();

        vector<string> strNums(n);

        // 元素轉成 string
        for (int i = 0; i < n; ++i) {
            strNums[i] = to_string(nums[i]);
        }

        sort(strNums.begin(), strNums.end(),
             [](string& a, string& b) { return a + b > b + a; });

        // 因為已經從大排到小了，最前面如果是 0，就直接返回 0
        if (strNums[0] == "0") {
            return "0";
        }

        string res;
        for (string s : strNums) res += s;

        return res;
    }
};

• T: $O(N \cdot N)$
• S: $O(N)$