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"
    
    

All Problems

All Solutions