jz45.把数组排成最小的数

题目描述

题解

这道题我首先是想通过回溯法进行全排列, 然后过程中更新最小值, 最后将该值输出. 但是使用这种方法超出了时间限制, 失败

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

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

"30"+"3"<"3"+"30", 所以有"30" < "3"

"5"+"9"<"9"+"5", 所以有"5"<"9"

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

既然牵扯到了排序, 以下通过Java内置排序功能(自定义比较器) 和快排两种方法进行实现:

内置排序

使用Java内置的排序功能, 自己编写比较器即可

public String minNumber(int[] nums) {
    String[] numsStrs = new String[nums.length];
    for (int i = 0; i < nums.length; i++) {
        numsStrs[i] = String.valueOf(nums[i]);
    }
    Arrays.sort(numsStrs, (x, y)->(x+y).compareTo(y+x));
    String res = "";
    for (String str : numsStrs) {
        res+=str;
    }
    return res;
}

快排

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

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

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

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

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

完整代码为:

public class jz45 {

    public String minNumber(int[] nums) {
        String[] numsStrList = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsStrList[i] = String.valueOf(nums[i]);
        }

        quickSort(numsStrList, 0, numsStrList.length - 1);
        String res = "";
        for (String str : numsStrList) {
            res += str;
        }
        return res;
    }

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

        int pIdex = partition(numsStrList, left, right);
        quickSort(numsStrList, left, pIdex - 1);
        quickSort(numsStrList, pIdex + 1, right);
    }

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

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


}