题目描述

给定一个字符串 s，s 包含以空格分隔的若干个单词，请对 s 进行如下处理后输出：

单词内部调整：对每个单词字母重新按字典序排序；
单词间顺序调整：
1. 统计每个单词出现的次数，并按次数降序排列；
2. 次数相同时，按单词长度升序排列；
3. 次数和单词长度均相同时，按字典序升序排列。

请输出处理后的字符串，每个单词以一个空格分隔。

输入描述

一行字符串，每个字符取值范围：[a-z, A-Z, 0-9] 以及空格" "，字符串长度范围：[1, 1000]

输出描述,

重新排序后的字符串，每个单词间隔 1 个空格，且首尾无空格

示例一

输入

This is an apple

输出

an is This aelpp

示例二

输入

My sister is in the house not in the yard

输出

in in eht eht My is not adry ehosu eirsst

解题思路

本题包含单词内和单词间的两种排序。先考虑单词内的排序，再考虑单词间的排序。

对于单词内的排序，需要对每个单词字母重新按字典序排序。所以我们在代码，对于lst中的每一个单词word：

用list(word)将字符串word转化为列表
用sorted()内置函数得到按照字典序排序的结果
用join()方法将排序结果重新转化为字符串

最后再使用列表推导式，可以得到每个单词内部进行排序后的新列表new_lst。

暂时无法在飞书文档外展示此内容

对于单词间的排序，需要依次考虑三个因素：

单词出现频率
单词长度
单词字典序

对于单词出现频率这个因素，我们很容易想到直接使用哈希表计数器Counter()来统计，即

cnt = Counter(new_lst)

而长度因素，可以很容易地使用len()内置函数得到。

所以我们使用lambda匿名函数来辅助new_lst的排序，即

new_lst.sort(key = lambda x: (-cnt[x], len(x), x))

要注意，由于要求按照单词出现频率降序排列，我们应该以-cnt[x]而不是cnt[x]做为第一个排序依据。

最后，还需要把new_lst的排序结果再一次使用join()方法合并为字符串并输出。注意合并时要用空格" "隔开每一个单词。

print(" ".join(new_lst))

代码

Python

# 题目：2023Q1A-字符串重新排列
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希表，排序
# 代码看不懂的地方，请直接在群上提问

from collections import Counter

lst = input().split()
n = len(lst)

# 单词内的排序：
# 对于lst中的每一个单词word：
# 1. 用list(word)转化为列表
# 2. 用sorted()内置函数得到按照字典序排序的结果
# 3. 用join()方法将排序结果重新转化为字符串
# 再使用列表推导式，可以得到新的列表
new_lst = ["".join(sorted(list(word))) for word in lst]

# 单词间的排序：
# 用Counter()统计new_lst中各个单词的出现频率
cnt = Counter(new_lst)
# 使用lambda匿名函数，
# 1. 先按照出现次数即cnt[x]排序，为了实现从大到小排序，需要以-cnt[x]为依据
# 2. 再按照长度len(x)排序
# 3. 最后再按照字典序排序
new_lst.sort(key = lambda x: (-cnt[x], len(x), x))

# 最后使用join()方法，将排序后的列表转化为字符串输出，记得用" "隔开
print(" ".join(new_lst))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] lst = scanner.nextLine().split(" ");
        int n = lst.length;

        List<String> newLst = new ArrayList<>();
        for (String word : lst) {
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            newLst.add(new String(chars));
        }

        Map<String, Integer> cnt = new HashMap<>();
        for (String word : newLst) {
            cnt.put(word, cnt.getOrDefault(word, 0) + 1);
        }

        Collections.sort(newLst, (a, b) -> {
            if (cnt.get(a).equals(cnt.get(b))) {
                if (a.length() == b.length()) {
                    return a.compareTo(b);
                }
                return a.length() - b.length();
            }
            return cnt.get(b) - cnt.get(a);
        });

        System.out.println(String.join(" ", newLst));
    }
}

C++

“`C++
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <sstream>
using namespace std;

int main() {
string input;
getline(cin, input);
stringstream ss(input);
vector<string> lst;
string word;

<pre><code>while (ss >> word) {
lst.push_back(word);
}

vector<string> newLst;
for (string word : lst) {
sort(word.begin(), word.end());
newLst.push_back(word);
}

map<string, int> cnt;
for (string word : newLst) {
cnt[word]++;
}

sort(newLst.begin(), newLst.end(), [&](const string &a, const string &b) {
if (cnt[a] == cnt[b]) {
if (a.length() == b.length()) {
return a < b;
}
return a.length() < b.length();
}
return cnt[a] > cnt[b];
});

for (int i = 0; i < newLst.size(); i++) {
cout << newLst[i];
if (i != newLst.size() – 1) {
cout << " ";
}
}
cout << endl;

return 0;
</code></pre>

}

“`

时空复杂度

时间复杂度：O(NlogN + Σ(MlogM))。单词内、单词间进行排序的时间复杂度

空间复杂度：O(N)。

Σ表示求和，M为每个单词的长度。

说明

华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。

机试分数越⾼评级越⾼，⼯资也就越⾼。

关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知

关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）