179.最大数

题目描述

题解

快排

这道题得通过排序来做, 如何排序, 也就是排序规则的制定就变成了解题的关键.

如果两个字符串x 和y , 若 x+y < y+x 则定义x>y , 注意, x 和y 都是字符串, 举例说明就是:

"30"+"3"<"3"+"30", 所以有"30" > "3", 把3排在左边

"5"+"9"<"9"+"5", 所以有"5">"9", 把9排在左边

给定一个字符串的数组, 将其按照以上规则进行排序, 然后将排序后的所有字符串按顺序拼接, 就是所能组成的最大数.

利用快排的方法, 将原数组按照上述的排序标准进行排序, 然后将字符串组拼接在一起即可.

整体都是套用快排的模板代码, 不同点在于比较的过程, 对整数数组进行排序时的代码为:

if(nums[i] < pivot){
    lt++;
    swap(nums, i, lt);
}

这是最基本的按照数值大小比较, 但是这道题要改为前面讨论过的比较标准:

if ((numsStr[i] + pivot).compareTo(pivot + numsStr[i]) > 0) {
    lt++;
    swap(numsStr, lt, i);
}

完整代码为:

public class lc179 {
    public String largestNumber(int[] nums) {

        StringBuilder res = new StringBuilder();

        int zeroCount = 0;

        if (nums.length < 1) {
            return res.toString();
        }
        String[] numsStr = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsStr[i] = String.valueOf(nums[i]);
            if (nums[i]==0){
                zeroCount++;
            }
        }
        if (zeroCount== nums.length){
            return "0";
        }
        quickSort(numsStr, 0, nums.length - 1);
        for (String s : numsStr) {
            res.append(s);
        }
        return res.toString();
    }

    private void quickSort(String[] numsStr, int left, int right) {
        if (left > right) {
            return;
        }

        int pIndex = partition(numsStr, left, right);
        quickSort(numsStr, left, pIndex - 1);
        quickSort(numsStr, pIndex + 1, right);
    }

    private int partition(String[] numsStr, int left, int right) {
        String pivot = numsStr[left];
        int lt = left;
        for (int i = left + 1; i <= right; i++) {
            if ((numsStr[i] + pivot).compareTo(pivot + numsStr[i]) > 0) {
                lt++;
                swap(numsStr, lt, i);
            }
        }
        swap(numsStr, lt, left);
        return lt;
    }

    private void swap(String[] numsStr, int i, int j) {
        String temp = numsStr[i];
        numsStr[i] = numsStr[j];
        numsStr[j] = temp;
    }
}