Leetcode:179. 最大数

题目描述

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

示例 1:

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

示例 2:

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

说明:

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

思路1：转化为排序+快排

将数组转化为字符串数组，然后从大到小排序，比较的是str(a)+str(b)与str(b)+str(a),若str(a)+str(b)大，则str(a) > str(b)

思路2: 转化为排序+Java排序

转化为排序然后使用Java内置排序

代码

代码1

class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0){
            return "";
        }
        StringBuilder result = new StringBuilder();
        String[] strNums = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strNums[i] = String.valueOf(nums[i]);
        }
        quickSort(strNums, 0, strNums.length - 1);
        if (strNums[0].equals("0")){
            return "0";
        }
        for(int i = 0; i < strNums.length; i++){
            result.append(strNums[i]);
        }
        return result.toString();
    }
    
    private void quickSort(String[] nums, int start, int end){
        if (start < end){
            int getIndex = getPartition(nums, start, end);
            quickSort(nums, start, getIndex);
            quickSort(nums, getIndex + 1, end);
        }
    }
    
    private int getPartition(String[] nums, int start, int end){
        String getNum = nums[start];
        nums[start] = nums[end];
        nums[end] = getNum;
        int getIndex = start;
        for(int i = start; i < end; i++){
            if (compare(nums[i], getNum)){
                String temp = nums[getIndex];
                nums[getIndex] = nums[i];
                nums[i] = temp;
                getIndex ++;
            }
        }
        nums[end] = nums[getIndex];
        nums[getIndex] = getNum;
        return getIndex;
    }
    
    private boolean compare(String a, String b){
        int aCount = a.length();
        int bCount = b.length();
        int maxCount = aCount > bCount ? aCount : bCount;
        char chA = '0';
        char chB = '0';
        for(int i = 0; i < aCount + bCount; i++){
            if (i < aCount){
                chA = a.charAt(i);
            }else{
                chA = b.charAt(i - aCount);
            }
            if(i < bCount){
                chB = b.charAt(i);
            }else{
                chB = a.charAt(i - bCount);
            }
            if (chA > chB){
                return true;
            }else if(chA < chB){
                return false;
            }
        }
        return false;
    }
}

代码2

class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0){
            return "";
        }
        StringBuilder result = new StringBuilder();
        String[] strNums = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            strNums[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strNums, new Comparator(){
            @Override
            public int compare(String a, String b){
                int aCount = a.length();
                int bCount = b.length();
                int maxCount = aCount > bCount ? aCount : bCount;
                char chA = '0';
                char chB = '0';
                for(int i = 0; i < aCount + bCount; i++){
                    if (i < aCount){
                        chA = a.charAt(i);
                    }else{
                        chA = b.charAt(i - aCount);
                    }
                    if(i < bCount){
                        chB = b.charAt(i);
                    }else{
                        chB = a.charAt(i - bCount);
                    }
                    if (chA != chB){
                        return chB - chA;
                    }
                }
                return 0;
            }
        });
        if (strNums[0].equals("0")){
            return "0";
        }
        for(int i = 0; i < strNums.length; i++){
            result.append(strNums[i]);
        }
        return result.toString();
    }
}

复杂度分析

思路1时间复杂度

最坏$O(n^2)$，平均$O(nlogn)$

思路1空间复杂度

$O(n)$

思路2时间复杂度

最坏$O(n^2)$，平均$O(nlogn)$

思路2空间复杂度

$O(n)$