力扣 179、最大数

一、题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

二、思路描述

要解决这个题目是有一个技巧的，就是排序的条件和正常的不太一样。我们看给一个数组进行排序的时候，只需要比较两个元素 (假设 x 和 y 是数组的任意两个元素) 的大小即可：
只要 x > y，那么降序排列的话 y 就应该排在 x 的后面
只要 x < y，那么降序排列的话 x 就应该排在 y 的后面
对于这道题目，假设 x 和 y 是数组中任意两个元素，那么 x 是需要排在 y 的前面还是后面呢？这个取决于 xy 和 yx 哪个大哪个小：
如果 xy > yx，那么 y 应该排在 x 的后面
如果 xy < yx，那么 x 应该排在 y 的后面
比如，x = 30， y = 3，那么 xy = 303，yx = 330，因为 xy < yx ，所以 30 应该在排在 3 的后面，这样就可以得到最大值

三、代码

    //179、最大数
    public String largestNumber(int[] nums) {
    
        // 排序
        quickSort(nums,0,nums.length-1);
        if(nums[0]==0)
            return "0";
        StringBuilder sb = new StringBuilder();

        for(int num:nums){
    
            sb.append(num);
        }
        return sb.toString();
    }

    public void quickSort(int[] nums, int l, int h) {
    
        if (l >= h)
            return;
        int pivot = nums[h];
        int less = l;
        int great = h;
        int i = l;
        while (i <= great) {
    
            String xy = nums[i] + "" + pivot;
            String yx = pivot + "" + nums[i];
            if (xy.compareTo(yx) > 0) {
    
                swap(nums, i, less);
                less++;
                i++;
            } else if (xy.compareTo(yx) < 0) {
    
                swap(nums, i, great);
                great--;
            } else {
    
                i++;
            }

        }
        quickSort(nums,l,less-1);
        quickSort(nums,great+1,h);
    }


    public void swap(int[] nums, int i, int j) {
    
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }