Java构造最小数字代码在N*log(N)限制下出现Time Limit Exception求助

超时原因分析 #

• 核心问题是末尾字符串拼接的时间复杂度达到了O(n²)：Java中String是不可变对象，每次执行ans += arr[j]都会生成一个新的String对象，需要复制之前所有字符再拼接新字符。当输入字符串长度很大（比如10^5级别）时，这部分的耗时会远超预期的线性时间，直接触发超时。
• 低效的字符转数字逻辑：Integer.parseInt(""+s.charAt(i))会先生成临时字符串再做解析，远不如直接用s.charAt(i) - '0'获取数字高效，额外增加了运行开销和GC压力。
• 冗余的数组转换步骤：完全可以直接操作字符数组完成排序和交换，不需要先转成int数组再逐位拼回字符串，多了两轮无意义的遍历开销。

优化后代码 #

优化后整体时间复杂度严格保持O(n log n)，可以轻松通过大用例测试：

import java.util.Arrays;

class Solution{
    public String minimum_Number(String s){
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        // 定位第一个非0字符
        int nonZeroIdx = 0;
        while(nonZeroIdx < arr.length && arr[nonZeroIdx] == '0') {
            nonZeroIdx++;
        }
        // 交换首位置和第一个非0字符，避免前导0
        if(nonZeroIdx < arr.length && arr[0] == '0') {
            char temp = arr[0];
            arr[0] = arr[nonZeroIdx];
            arr[nonZeroIdx] = temp;
        }
        return new String(arr);
    }
}

内容的提问来源于stack exchange，提问作者Mahipal Singh Sisodia