P203 拼接的最大数字

描述#

这个题目说的是，给你一个数组，数组中的元素都是非负整数。你要重新排列这些整数，使得它们拼接后的数字最大，并返回这个数字。由于拼接后的数字可能非常大，因此结果以字符串的形式返回。

比如说，给你的非负整数数组是：
12, 8
数组中有两个元素，可以拼接成 "128" 或是 "812"。因此，拼接成的最大数字就是 "812"。注意，结果是一个字符串。
再比如说，给你的数组是：
3, 31, 36, 4, 8
这个数组可以拼接成的最大数字是 "8436331"。

代码#

public class AlgoCasts {

  // Time: O(n*log(n)), Space: O(n)
  public String largestNumber(int[] nums) {
    if (nums == null || nums.length == 0) return "";
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; ++i) {
      strs[i] = String.valueOf(nums[i]);
    }
    Arrays.sort(strs, (o1, o2) -> {
      String o12 = o1 + o2;
      String o21 = o2 + o1;
      return o21.compareTo(o12);
    });
    if (strs[0].equals("0")) return "0";
    StringBuilder sb = new StringBuilder();
    for (String str: strs) sb.append(str);
    return sb.toString();
  }

  // Time: O(n*log(n)), Space: O(n)
  public String largestNumberFast(int[] nums) {
    if (nums == null || nums.length == 0) return "";
    String[] strs = new String[nums.length];
    for (int i = 0; i < nums.length; ++i) {
      strs[i] = String.valueOf(nums[i]);
    }
    Arrays.sort(strs, (o1, o2) -> {
      int n1 = o1.length(), n2 = o2.length();
      for (int i = 0; i < n1+n2; ++i) {
        char c1 = i < n1 ? o1.charAt(i) : o2.charAt(i-n1);
        char c2 = i < n2 ? o2.charAt(i) : o1.charAt(i-n2);
        if (c1 == c2) continue;
        return c2 - c1;
      }
      return 0;
    });
    if (strs[0].equals("0")) return "0";
    StringBuilder sb = new StringBuilder();
    for (String str: strs) sb.append(str);
    return sb.toString();
  }

}