LeetCode 179. Largest Number

[Woodyiiiiiii]

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

---

这题是要形成最大数字，以字符串形式表示。我一开始想着从数字方面入手，其实肯定是要先把数字转换成字符串的，有两种方式：String.valueOf(int)或者Integer.toString(int)。

接下来就是要选择最大的数字，方法是拼接字符串，最后利用compareTo比较字符串就行了。

选择排序做法：

class Solution {
    public String largestNumber(int[] nums) {
        StringBuilder sb = new StringBuilder();
        int n = nums.length;
        String[] strs = new String[n];
        int i = 0, j = 0;
        for (; i < n; ++i) {
            strs[i] = String.valueOf(nums[i]);
        }
        for (i = 1; i <= n; ++i) {
            int idx = -1;
            for (j = 0; j < n; ++j) {
                if (nums[j] == -1) {
                    continue;
                }
                if (idx == -1 || isFind(strs[idx], strs[j])) {
                    idx = j;
                }
            }
            sb.append(strs[idx]);
            nums[idx] = -1;
        }
        String res = new String(sb);
        for (i = 0; i < res.length(); ++i) {
            if (res.charAt(i) != '0') {
                return res;
            }
        }
        return "0";
    }
    public boolean isFind(String s1, String s2) {
        String t1 = s1 + s2, t2 = s2 + s1;
        return t2.compareTo(t1) > 0;
    }
}

class Solution {
    public String largestNumber(int[] nums) {
        String num_str[] = new String[nums.length];
        int i = 0; 
        for(int num : nums) {
            num_str[i++] = String.valueOf(num); 
        }
        Arrays.sort(num_str, (a,b) -> (b+a).compareTo(a+b));
        if(num_str[0].equals("0")) {
            return "0";
        }
		StringBuilder sb = new StringBuilder();
        for(String s : num_str) {
            sb.append(s); 
        }
        return sb.toString();
    }
}

在Discussin中看到其他人的用comparator的Arrays.sort做法，利用了Java新特性：

class Solution {
    public String largestNumber(int[] nums) {
        String num_str[] = new String[nums.length];
        int i = 0; 
        for(int num : nums) {
            num_str[i++] = String.valueOf(num); 
        }
        Arrays.sort(num_str, (a,b) -> (b+a).compareTo(a+b));
        if(num_str[0].equals("0")) {
            return "0";
        }
		StringBuilder sb = new StringBuilder();
        for(String s : num_str) {
            sb.append(s); 
        }
        return sb.toString();
    }
}

---

• https://leetcode.com/problems/largest-number/
• https://leetcode.com/problems/largest-number/discuss/853855/Java-4ms-or-Comparator