leetcode-179-Largest-Number

描述

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1 2	Input: [10,2] Output: "210"

Example 2:

1 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.

分析

又是一道自定义排序算法的问题。有两个需要注意的地方，1，虽然这里是按照大小排序，数字更大的排在前面，也要考虑两个数字之间的组合情况，比如下面的测试用例：

Input:[3,30,34,5,9]

Output:”9534303”

Expected:”9534330”

如果只考虑两两的大小比较，”30” > “3”，而真实情况是 “330” > “303”，因此我们应该比较两两组合之后的字符串。

需要考虑 [0, 0] 这样的 corner case，对于 [0, 0] 如果不做特殊处理，会返回 “00”，而实际上我们只需要 “0”。

解决方案1(Java)

class Solution {
    public String largestNumber(int[] nums) {
        if (nums.length == 0) {
            return "";
        }
        
        String[] nums2Strings = new String[nums.length];
        
        for (int i = 0; i < nums.length; i++) {
            nums2Strings[i] = String.valueOf(nums[i]);
        }
        
        Arrays.sort(nums2Strings, new Comparator<String>() {
           public int compare(String s1, String s2) {
               String s1s2 = s1 + s2;
               String s2s1 = s2 + s1;
               return s2s1.compareTo(s1s2);
           } 
        });
        
        if (nums2Strings[0].equals("0")) {
            return "0";
        }
        
        StringBuilder result = new StringBuilder();
        
        for (String str: nums2Strings) {
            result.append(str);
        }
        return result.toString();
    }
}

描述

分析

解决方案1(Java)

题目来源