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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。