Given a list of non-negative integers nums
, arrange them such that they form the largest number.
Note: 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"
Example 3:
Input: nums = [1] Output: "1"
Example 4:
Input: nums = [10] Output: "10"
Constraints:
1 <= nums.length <= 100
0 <= nums[i] <= 109
Solution: Greedy
Sort numbers by lexical order.
e.g. 9 > 666
Time complexity: O(nlogn)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: string largestNumber(vector<int> &num) { vector<string> s; for (int x : num) s.emplace_back(to_string(x)); sort(begin(s), end(s), [](const auto& s1, const auto& s2) { return s1 + s2 > s2 + s1; }); if (s[0] == "0") return "0"; string ans; for (int i = 0; i < s.size(); ++i) ans += s[i]; return ans; } }; |