LEETCODE 179. Largest Number 解题思路分析

题目大意：

最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210

示例 2:

输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=179

解题思路分析：

这道题的关键是排序，排序方法既不是按照数字大小，也不是字典顺序。比如，数字21和2，不论是数值大小还是字典顺序，21都应该大于2，但结果却不是212，而应该是221。因此我们需要自己写一个排序方法，排序时，为了方便，先将所有数字转化为字符串，对于任意两个字符串s1和s2，比较s1+s2与s2+s1，如果前者字典顺序大，我们就将s1放在s2前面，反之s2在s1前面。

实现代码：

public String largestNumber(int[] nums) {
    // 新建一个字符串数组
    String[] arr = new String[nums.length];
    // 将int数组转化为字符串数组
    for(int i=0;i<nums.length;i++){
        arr[i]=String.valueOf(nums[i]);
    }
    // 降序排序，按照字典顺序比较s2+s1与s1+s2
    Arrays.sort(arr, (s1,s2)-> (s2+s1).compareTo(s1+s2));
    // 如果数组最大值为0，直接返回0
    if("0".equals(arr[0])) return "0";
    // 将排序好的数组按顺序拼接并返回
    StringBuilder sb = new StringBuilder();
    for(String s : arr) sb.append(s);
    return sb.toString();
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 23.56% of Java online submissions for Largest Number.

Memory Usage: 42.5 MB, less than 6.67% of Java online submissions for Largest Number.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-179-largest-number-解题思路分析/