179. 最大数

本题来自LeetCode：179. 最大数^[1]

题目描述

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

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

示例 2:

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

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

解法一

题目分析

本题本质上是一道排序题，主要逻辑在比较函数。为了让结果最大，需要最高位的数字越大越好。对于 a、 b两个数值，如何比较其大小？可以通过将其转换两个字符串来比较： a + b、 b + a。这样两个字符串的长度相等，可以直接逐位比较高位的数字大小。
本解法采用插入排序法，当前也可以采用其他排序算法。

题目解答

class Solution {
    public String largestNumber(int[] nums) {
        StringBuilder sb = new StringBuilder();
        // 排序，降序排列
        for(int i = 0; i  nums.length; i ++) {
            for(int j = i + 1; j  nums.length; j ++) {
                String num1 = nums[i] + "" + nums[j];
                String num2 = nums[j] + "" + nums[i];
                if(num1.compareTo(num2)  0) {
                    swap(nums, i, j);
                }
            }
            sb.append(nums[i]);
            
            // 表示该数组的值全部为0，可直接返回
            if(i == 0 && nums[0] == 0) {
                break;
            }
        }
        
        return sb.toString();
    }
    // 交换i和j
    public void swap(int[] nums, int i, int j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

复杂度分析：
时间复杂度： O(n^2)
空间复杂度： O(1)

解法二

题目分析

比较两个数的大小，有两种情况：

若一个数是另一个数的前缀，比如`34`是`343`的前缀。我们需要将比较的长度弄成一样长。应该用`343434`和`343343`来比较。

两个数互不为前缀，那么直接从高至低逐位比较即可。

题目解答

class Solution {
    public String largestNumber(int[] nums) {
        StringBuilder sb = new StringBuilder();
        // 排序，降序排列
        for(int i = 0; i  nums.length; i ++) {
            for(int j = i + 1; j  nums.length; j ++) {
                if(shouldSwap(nums[i], nums[j])) {
                    swap(nums, i, j);
                }
            }
            sb.append(nums[i]);
            
            // 表示该数组的值全部为0，可直接返回
            if(i == 0 && nums[0] == 0) {
                break;
            }
        }
        
        return sb.toString();
    }
    // 交换i和j
    public void swap(int[] nums, int i, int j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }

    // a  b : true
    // a = b : false
    public boolean shouldSwap(int a, int b) {
        char[] arrayA = String.valueOf(a).toCharArray();
        char[] arrayB = String.valueOf(b).toCharArray();
        // 最大公约数
        int gcd = gcd(arrayA.length, arrayB.length);
        // 最小公倍数
        int lcm = arrayA.length * arrayB.length / gcd;
        for(int i = 0; i  lcm; i ++) {
            char charA = arrayA[i % arrayA.length];
            char charB = arrayB[i % arrayB.length];
            if(charA == charB) {
                continue;
            }
            return charA  charB;
        }
        return false;
    }
    // 获取最大公约数
    public int gcd(int lengthA, int lengthB) {
        while(lengthB != 0) {
            int remainder = lengthA % lengthB;
            lengthA = lengthB;
            lengthB = remainder;
        }
        return lengthA;
    }
}

复杂度分析：
时间复杂度： O(n^2)
空间复杂度： O(1)

参考资料

179. 最大数: https://leetcode-cn.com/problems/largest-number

原文始发于微信公众号（xiaogan的技术博客）：