力扣刷题-179.最大数

以你之姓@ 2022-12-21 15:53 123阅读 0赞

## 179.最大数 ##

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

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/largest-number

示例 1：

输入：nums = [10,2]
    输出："210"
    示例 2：
    
    输入：nums = [3,30,34,5,9]
    输出："9534330"
    示例 3：
    
    输入：nums = [1]
    输出："1"
    示例 4：
    
    输入：nums = [10]
    输出："10"

提示：

1 <= nums.length <= 100
    0 <= nums[i] <= 109

## 官方分析 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70_pic_center]

class Solution {
        
        private class LargerNumberComparator implements Comparator<String> {
        
            @Override
            public int compare(String a, String b) {
        
                String order1 = a + b;
                String order2 = b + a;
               return order2.compareTo(order1);
            }
        }
    
        public String largestNumber(int[] nums) {
        
            // Get input integers as strings.
            String[] asStrs = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
        
                asStrs[i] = String.valueOf(nums[i]);
            }
    
            // Sort strings according to custom comparator.
            Arrays.sort(asStrs, new LargerNumberComparator());
    
            // If, after being sorted, the largest number is `0`, the entire number
            // is zero.
            if (asStrs[0].equals("0")) {
        
                return "0";
            }
    
            // Build largest number from sorted array.
            String largestNumberStr = new String();
            for (String numAsStr : asStrs) {
        
                largestNumberStr += numAsStr;
            }
    
            return largestNumberStr;
        }
    }

复杂度分析

时间复杂度：O(nlgn)O(nlgn)

尽管我们在比较函数中做了一些额外的工作，但是这只是一个常数因子。所以总的时间复杂度是由排序决定的，在 Python 和 Java 中都是 O(nlgn)O(nlgn) 。

空间复杂度：O(n)O(n)

这里，我们使用了 O(n)O(n) 的额外空间去保存 nums 的副本。尽管我们就地进行了一些额外的工作，但最后返回的数组需要 O(n)O(n) 的空间。因此，需要的额外空间与 nums 大小成线性关系。

解题代码

class Solution {
        
         private class LargerNumberComparator  implements Comparator<String>{
        
            public int compare(String a,String b){
        
                String order1 =a+b;
                String order2 =b+a;
                return order2.compareTo(order1);
            }
        }
        public String largestNumber(int[] nums) {
        
            
            String[] strings = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
        
                strings[i] = String.valueOf(nums[i]);
            }
            Arrays.sort(strings, new LargerNumberComparator());
            if (strings[0].equals("0")) {
        
                return "0";
            }
            String largestNumberStr = new String();
            for (String numStr : strings) {
        
                largestNumberStr += numStr;
            }
    
            return largestNumberStr;
        
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70_pic_center 1]  
IDEA运行代码

package cn.test;
    
    import java.util.Arrays;
    import java.util.Comparator;
    import java.util.Scanner;
    
    /**
     * @ClassName Demo01
     * @Description 自定义排序
     * @Author 郑万富
     * @Date 2020/11/16 22:53
     * @Version 1.0
     */
    public class Demo01 {
        
        public static void main(String[] args) {
        
            Solution s = new Solution();
           System.out.println("请输入数组长度：");
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            System.out.println("请输入数组元素：");
            int[] arr = new int[n];
            for (int i = 0; i <arr.length ; i++) {
        
                arr[i]=sc.nextInt();
            }
           // int num []={10,2};
            System.out.println(s.LargestNumber(arr));
        }
    
    }
    class Solution{
        
    
        private class LargerNumberComparator  implements Comparator<String>{
        
            public int compare(String a,String b){
        
                String order1 =a+b;
                String order2 =b+a;
                return order2.compareTo(order1);
            }
        }
        public String LargestNumber(int []nums) {
        
            String[] strings = new String[nums.length];
            for (int i = 0; i < nums.length; i++) {
        
                strings[i] = String.valueOf(nums[i]);
            }
            Arrays.sort(strings, new LargerNumberComparator());
    
            if (strings[0].equals("0")) {
        
                return "0";
            }
            String largestNumberStr = new String();
            for (String numStr : strings) {
        
                largestNumberStr += numStr;
            }
    
            return largestNumberStr;
        }
    }

![在这里插入图片描述][20201116233329136.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1c374afc63ca4a8b9ffcf77ff7708368.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201116233133361.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjA0NzI4NQ==,size_16,color_FFFFFF,t_70#pic_center
[20201116233329136.png_pic_center]: https://img-blog.csdnimg.cn/20201116233329136.png#pic_center