题解 | #最大数#

import java.util.*;


public class Solution {
    /**
     * 最大数
     * @param nums int整型一维数组 
     * @return string字符串
     */
    public String solve (int[] nums) {
        // write code here
        
        // 一些特殊情况的处理
        if (1 == nums.length) {
            return nums[0] + "";
        }
        // 调用快排，对数组 nums 进行排序
        quickSort(nums, 0, nums.length - 1);
        // 定义一个 StringBuffer，用于存放最终的返回结果
        StringBuffer rs = new StringBuffer("");
        for (int i = nums.length - 1; i > -1; i--) {
            rs.append(nums[i] + "");
        }
        
        // [0,0]
        int index = 0; // 截取位置
        for (int i = 0; i < rs.length(); i++) {
            if (rs.charAt(i) != '0') {
                break;
            }
            index++;
        }
        String rsString = rs.substring(index); // 将头部的 0 全部截取出去
        if ("".equals(rsString)) {
            return "0";
        }
        
        return rsString;
    }
    
    // 快排的具体实现
    public void quickSort(int[] nums, int start, int end) {
        
        // 别忘了终止条件
        if (start >= end) {
            return;
        }
        
        // 荷兰国旗问题
        int lp = start - 1; // 小于区域
        int rp = end + 1; // 大于区域
        int p = start; // 当前指针
        
        int tmpValue = nums[end]; // 获取数组 nums 的最后一位上的数字
        int swap; // 定义一个整型变量，用于协助两个数字进行交换
        
        while (p != rp) {
            if (comparaString(nums[p], tmpValue) == -1) {
                // 将小于区域右一位上的数字与当前数字进行交换
                swap = nums[p];
                nums[p] = nums[lp + 1];
                nums[lp + 1] = swap;
                // 小于区域向右扩张
                lp++;
                // 别忘了，当前指针也要向右移一位
                p++;
            }
            else if (comparaString(nums[p], tmpValue) == 0) {
                // 当前指针向右移一位即可
                p++;
            }
            else {
                // 将大于区域左一位上的数字与当前数字进行交换
                swap = nums[p];
                nums[p] = nums[rp - 1];
                nums[rp - 1] = swap;
                // 大于区域向左扩张
                rp--;
                // 当前指针不需要进行移动！！！
                p = p;
            }
        }
        // 以上代码实现了荷兰国旗的问题
        // 接下来进行递归调用
        quickSort(nums, start, lp);
        quickSort(nums, rp, end);
        return;
    }
    
    // 自定义一个函数，用来比较两个数的大小(注意，根据题目的要求，此处的大小应该是字典序的大小，而不是单纯的两个数字的大小比较)
    public int comparaString (int num1, int num2) {
        // 将 int 类型转换为 String 类型
        String num1Str = num1 + "";
        String num2Str = num2 + "";
        int len1 = num1Str.length();
        int len2 = num2Str.length();
        int p1 = 0;
        int p2 = 0;
        while (p1 < len1 && p2 < len2) { // 防止越界
            if (num1Str.charAt(p1) < num2Str.charAt(p2)) {
                return -1;
            }
            else if (num1Str.charAt(p1) > num2Str.charAt(p2)) {
                return 1;
            }
            else {
                p1++;
                p2++;
            }
        }
        if (len1 == len2) {
            return 0;
        }
        else if (len1 < len2) {
            if (num2Str.charAt(p2) < num1Str.charAt(0)) {
                return 1;
            }
            else if (num2Str.charAt(p2) > num1Str.charAt(0)) {
                return -1;
            }
            else {
                return 0;
            }
        }
        else {
            if (num1Str.charAt(p1) < num2Str.charAt(0)) {
                return -1;
            }
            else if (num1Str.charAt(p1) > num2Str.charAt(0)) {
                return 1;
            }
            else {
                return 0;
            }
        }
    }
}