题目描述

「句子」是一个用空格分隔单词的字符串。给你一个满足下述格式的句子 text :

句子的首字母大写
text 中的每个单词都用单个空格分隔。
请你重新排列 text 中的单词，使所有单词按其长度的升序排列。如果两个单词的长度相同，则保留其在原句子中的相对顺序。

请同样按上述格式返回新的句子。

样例

输入：text = "Leetcode is cool"
输出："Is cool leetcode"
解释：句子中共有 3 个单词，长度为 8 的 "Leetcode" ，长度为 2 的 "is" 以及长度为 4 的 "cool" 。
输出需要按单词的长度升序排列，新句子中的第一个单词首字母需要大写。

输入：text = "Keep calm and code on"
输出："On and keep calm code"
解释：输出的排序情况如下：
"On" 2 个字母。
"and" 3 个字母。
"keep" 4 个字母，因为存在长度相同的其他单词，所以它们之间需要保留在原句子中的相对顺序。
"calm" 4 个字母。
"code" 4 个字母。

输入：text = "To be or not to be"
输出："To be or to be not"

提示：

• text 以大写字母开头，然后包含若干小写字母以及单词间的单个空格。
• 1 <= text.length <= 10^5

算法分析

排序

• 1、用结构体存储每个单词的位置idx，长度len，单词s，对所有单词按照长度len从小到大排序，若长度len相同则按照位置idx，从小到大排序
• 2、排序后对依次输出单词
• 3、注意：排序前需要将第一个单词的第一个元素将大写变成小写，保证排序的数组全是小写，排序后输出时需要将第一个单词的第一元素将小写变成大写

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    static int N = 100010;
    static Edge[] edge = new Edge[N];
    public String arrangeWords(String text) {
        String[] s1 = text.split(" ");
        int n = s1.length;
        for(int i = 0;i < n;i ++)
        {
            if(i == 0)
            {
                s1[0] = (char)(s1[0].charAt(0) + 'a' - 'A') + s1[0].substring(1,s1[0].length());
            }
            int len = s1[i].length();
            edge[i] = new Edge(i,len,s1[i]);
        }
        Arrays.sort(edge,0,n);
        String ans = "";
        for(int i = 0;i < n;i ++)
        {
            if(i == 0) edge[0].s = (char)(edge[0].s.charAt(0) - ('a' - 'A')) + edge[0].s.substring(1,edge[0].s.length());
            if(i != n - 1) ans += edge[i].s + " ";
            else ans += edge[i].s;
        }
        return ans;
    }
}
class Edge implements Comparable<Edge>
{
    int idx;
    int len;
    String s;
    Edge(int idx,int len,String s)
    {
        this.idx = idx;
        this.len = len;
        this.s = s;
    }
    @Override
    public int compareTo(Edge o) {
        return len == o.len ? Integer.compare(idx, o.idx) : Integer.compare(len, o.len);
    }
}