Question
Formatted question description: https://leetcode.ca/all/179.html
179. Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
Example 1:
Input: [10,2]
Output: "210"
Example 2:
Input: [3,30,34,5,9]
Output: "9534330"
Note: The result may be very large, so you need to return a string instead of an integer.
@tog-top100
Algorithm
For two numbers a and b, if you convert them to strings, if ab> ba, then a will be ranked first,
- For example, 9 and 34, since 934>349, 9 is in front,
- For example, 30 and 3, because 303<330, 3 is in front of 30.
After sorting the original array according to this rule, converting each number into a string and then concatenating it is the final result.
Code
Java
-
import java.util.Arrays; import java.util.Comparator; public class Largest_Number { class Solution { public String largestNumber(int[] nums) { // Get input integers as strings. String[] asStrs = new String[nums.length]; for (int i = 0; i < nums.length; i++) { asStrs[i] = String.valueOf(nums[i]); } // Sort strings according to custom comparator. Arrays.sort(asStrs, new LargerNumberComparator()); // If, after being sorted, the largest number is `0`, the entire number // is zero. if (asStrs[0].equals("0")) { return "0"; } // Build largest number from sorted array. String largestNumberStr = new String(); for (String numAsStr : asStrs) { largestNumberStr += numAsStr; } return largestNumberStr; } private class LargerNumberComparator implements Comparator<String> { @Override public int compare(String a, String b) { String order1 = a + b; String order2 = b + a; return order2.compareTo(order1); } } } }
-
// OJ: https://leetcode.com/problems/largest-number/ // Time: O(NlogN * W) where W is the max length of the number strings. // Space: O(NW) class Solution { public: string largestNumber(vector<int>& A) { vector<string> v; for (int n : A) v.push_back(to_string(n)); sort(begin(v), end(v), [](auto &a, auto &b) { for (int i = 0; i < a.size() + b.size(); ++i) { char x = i < a.size() ? a[i] : b[i - a.size()], y = i < b.size() ? b[i] : a[i - b.size()]; if (x != y) return x > y; } return false; // don't return true which will result in infinite loop }); if (v[0] == "0") return "0"; string ans; for (auto &s : v) ans += s; return ans; } };
-
class Solution: # @param {integer[]} nums # @return {string} def largestNumber(self, nums): def cmpFunc(a, b): stra, strb = str(a), str(b) if stra + strb < strb + stra: return -1 elif stra + strb > strb + stra: return 1 else: return 0 nums.sort(cmp=cmpFunc, reverse=True) return "".join(str(num) for num in nums) if sum(nums) != 0 else "0"