题目

179. 最大数

剑指 Offer 45. 把数组排成最小的数

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

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

示例 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

代码

刚一开始这个题我是不会做的，只能靠看看别人的题解勉强过日子，就这个样子。

我能看懂的也就是调用Arrays.sort函数并且自定义比较函数接口以及使用快排自定义排序。

这里我们就用一下快排，下面的图是算法导论上的快排模板

class Solution {
   
    public String largestNumber(int[] nums) {
   
        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);
        StringBuilder sb = new StringBuilder();
        for(String s : strNums) {
   
            sb.append(s);
        }
        String res = sb.toString();
        return res.charAt(0) == '0' ? "0" : res;
    }

    public void quickSort(String[] array, int left, int right) {
   
        if(left < right) {
   
            int pivot = partition(array, left, right);
            quickSort(array, left, pivot - 1);
            quickSort(array, pivot + 1, right);
        }
    }

    public int partition(String[] array, int left, int right) {
   
        int pivot = left;
        int index = left + 1;
        for(int i = index; i <= right; i++) {
   
            if((array[i] + array[pivot]).compareTo(array[pivot] + array[i]) >= 0) {
   
                swap(array, i, index);
                index++;
            }
        }
        swap(array, pivot, index - 1);
        return index - 1;
    }

    public void swap(String[] array, int a, int b) {
   
        String temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

解析

我们想一想，怎么排这个数组，才能让它的结果是最大的呢？
[3,30,34,5,9]

首先是直观上来说，我们一定要把9放在第一位，5放在第二位，这是毋庸置疑的。比如我们有一个数组[1, 2, 3, 4, 5, 6, 7, 8, 9]，要你你怎么排？自然是排成[9, 8, 7, 6, 5, 4, 3, 2, 1]。

所以我们先排一下，[9, 5, 3, 30, 34]，那么问题又出现了，3、30、34之间应该怎么排序呢？

  • 3、30组成330，而30、3则组成303，说明3应该放在30前面
  • 3、34组成334，而34、3组成343，所以34应该放在3的前面

所以3、30、34应该排成34330这种形式。

那么我们如何确定5应该放在这些3开头的数字之前呢？也是一样的，5与任何3开头的数字组合在一起，一定是5开头的最大。比如5和34放在一起，一定是534 > 345。

这样排序规则就很清晰了，只要XY（组合成字符串）大于YX，那么X就应该放在Y前面。

所以整个快排模板几乎不用动，我们只需要改变partition里面的比较规则即可：

for(int i = index; i <= right; i++) {
   
     if((array[i] + array[pivot]).compareTo(array[pivot] + array[i]) >= 0) {
   
         swap(array, i, index);
         index++;
     }
}

我们设array[i]的字符串为X，array[pivot]的字符串为Y，
如果XY > YX，则将X放在左边，这一次遍历后效果应该是类似于下图

只是个类似，数量都不对应。

只要知道了怎么排，知道了比较的条件，写快排应该还是很容易的。