pythonjavacjsc_0">【华为OD-E卷 - 字符统计及重排 100分（python、java、c++、js、c）】
题目
给出一个仅包含字母的字符串，不包含空格，统计字符串中各个字母（区分大小写）出现的次数，并按照字母出现次数从大到小的顺序。
输出各个字母及其出现次数。如果次数相同，按照自然顺序进行排序，且小写字母在大写字母之前
输入描述
- 输入一行，为一个仅包含字母的字符串
输出描述
- 按照字母出现次数从大到小的顺序输出各个字母和字母次数，用英文分号分隔，注意末尾的分号；
字母和次数间用英文冒号分隔
用例
用例一：
输入：
xyxyXX
输出：
x:2;y:2;X:2;
用例二：
输入：
abababb
输出：
b:4;a:3;
python_50">python解法
- 解题思路：
- 统计字符频次：
通过遍历输入字符串 text，使用字典 freq 统计每个字符的出现次数。
字典的键是字符，值是该字符的出现次数。
自定义排序：
使用 compare(x, y) 函数自定义排序规则：
第一优先级：按照字符出现次数降序排序（出现次数多的排前面）。
第二优先级：如果两个字符出现次数相同，按以下规则比较：
同类字符（均为小写或均为大写）：按字典序升序排序。
不同类字符（一个大写、一个小写）：小写字母排在前面，大写字母排在后面。
排序并格式化输出：
使用 sorted() 函数，将字符频次字典转换为列表并按 compare 规则排序。
通过列表推导式将排序后的字符频次转换为格式 字符:次数; 形式的字符串
使用到的算法
哈希表（字典）：用于统计字符频次，时间复杂度为 O(n)（n 为字符串长度）。
自定义排序（基于 cmp_to_key 的比较器）：
基于比较器的排序（cmp_to_key）：时间复杂度 O(m log m)，其中 m 为不同字符的数量。
排序规则：
先按出现次数降序排列。
频次相同情况下：
同类型字符（大写或小写）：按字典序升序排列。
不同类型字符（小写优先）。
字符串拼接：遍历排序后的列表并拼接结果，时间复杂度 O(m)
python">import functools# 获取输入字符串
text = input()def compare(x, y):"""自定义比较函数，用于排序字符频次表:param x: (字符, 频次) 元组1:param y: (字符, 频次) 元组2:return: 负数（x < y）, 0（相等）, 正数（x > y）"""# 1. 先按出现次数降序排序if x[1] != y[1]:return y[1] - x[1]# 2. 处理相同频次的字符：# - 同类型字符（都小写或都大写），按字典序升序排列if (x[0].islower() and y[0].islower()) or (x[0].isupper() and y[0].isupper()):return 1 if x[0] > y[0] else -1# 3. 小写字母排在前面，大写字母排在后面return 1 if x[0].isupper() else -1def result():"""计算字符频次，并按规则排序后格式化输出:return: 格式化的结果字符串"""# 1. 统计字符频次freq = {}for ch in text:freq[ch] = freq.get(ch, 0) + 1# 2. 将字典转换为 (字符, 频次) 元组列表freq_list = list(freq.items())# 3. 使用自定义排序函数进行排序freq_list.sort(key=functools.cmp_to_key(compare))# 4. 拼接结果字符串return "".join([f"{k}:{v};" for k, v in freq_list])# 输出结果
print(result())java_129">java解法
- 解题思路
- 字符频次统计
读取用户输入的字符串 input。
使用 TreeMap<Character, Integer> 统计字符串中各字符的出现次数：
TreeMap 具有自动排序功能，默认按照 字典序 排序键（字符）。
自定义排序
使用 PriorityQueue 进行 自定义排序：
第一优先级：按出现次数降序排序（频次越高，优先级越高）。
第二优先级（出现次数相同时）：
若两个字符 均为小写 或 均为大写，按字典序升序排列。
若一个字符为 小写，另一个为 大写，小写优先，大写在后。
格式化输出
依次从 PriorityQueue 取出字符及其出现次数，拼接成 字符:次数; 的格式字符串并返回
用到的算法
哈希表（TreeMap）：
用于 统计字符频次，时间复杂度为 O(n)（n 为字符串长度）。
由于 TreeMap 自动排序，默认 字典序 排序键（字符），但不影响自定义排序。
优先队列（PriorityQueue）：
维护一个 最大堆 进行 自定义排序，用于 按照频次降序排列，时间复杂度 O(m log m)（m 为不同字符数）。
排序规则：
按字符出现次数降序。
出现次数相同：
同类字符（均小写/均大写） 按 字典序升序 排列。
小写字母优先，大写字母在后。
字符串拼接（StringBuilder）：
由于 Java 中字符串拼接 String 需要新建对象，因此用 StringBuilder 优化。
复杂度 O(m)
java">import java.util.*;public class Main {public static void main(String[] args) {// 读取输入字符串Scanner scanner = new Scanner(System.in);String input = scanner.nextLine();scanner.close();// 计算字符频次并输出结果System.out.println(calculateFrequency(input));}public static String calculateFrequency(String input) {// 1. 使用 TreeMap 统计字符频次，并按照字典序自动排序TreeMap<Character, Integer> charCountMap = new TreeMap<>();for (char ch : input.toCharArray()) {charCountMap.put(ch, charCountMap.getOrDefault(ch, 0) + 1);}// 2. 使用优先队列（最大堆），根据自定义规则排序PriorityQueue<Map.Entry<Character, Integer>> queue = new PriorityQueue<>((a, b) -> {// (1) 先按照字符出现次数降序排列if (!a.getValue().equals(b.getValue())) {return b.getValue() - a.getValue();} // (2) 出现次数相同时，按以下规则排序：else {// (2.1) 如果两个字符都是小写或都是大写，按字典序升序排序if (Character.isLowerCase(a.getKey()) && Character.isLowerCase(b.getKey())) {return a.getKey() - b.getKey();} if (Character.isUpperCase(a.getKey()) && Character.isUpperCase(b.getKey())) {return a.getKey() - b.getKey();}// (2.2) 小写字母优先，大写字母在后return Character.isLowerCase(a.getKey()) ? -1 : 1;}});// 3. 将统计结果放入优先队列queue.addAll(charCountMap.entrySet());// 4. 依次取出排序后的字符和频次，拼接结果字符串StringBuilder result = new StringBuilder();while (!queue.isEmpty()) {Map.Entry<Character, Integer> entry = queue.poll();result.append(entry.getKey()).append(":").append(entry.getValue()).append(";");}// 5. 返回格式化字符串return result.toString();}
}C++解法
- 解题思路
- 字符频次统计
读取输入字符串 input。
使用 map<char, int>（有序映射） 统计各字符的出现次数：
键（char）为字符，值（int）为出现次数。
map 默认按照 字典序排序 键（字符）。
自定义排序
将 map 转换为 vector<pair<char, int>>，以便使用 sort() 自定义排序：
第一优先级：按出现次数降序排序（频次高的字符排前）。
第二优先级（出现次数相同时）：
小写字母优先（islower()）。
同类字符（均为小写或均为大写） 按 字典序升序 排序。
格式化输出
遍历排序后的 vector，拼接成 字符:次数; 格式的字符串
使用到的算法
哈希表（map）：
统计字符频次，时间复杂度 O(n)（n 为字符串长度）。
map 采用 红黑树（RB-Tree） 实现，插入元素的复杂度 O(log m)，m 为不同字符数。
自定义排序（sort() + lambda）：
排序优先级：
按频次降序（O(m log m)）。
频次相同：
小写字母优先。
同类字符（小写/大写） 按 字典序升序。
字符串拼接（stringstream）：
stringstream 处理拼接，避免 string 频繁 + 操作（O(m)）
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <sstream>using namespace std;/*** 计算字符频次并进行排序* @param input 输入字符串* @return 格式化后的频次字符串*/
string calculateFrequency(const string& input) {// 1. 使用 map 统计字符出现次数（按字典序自动排序）map<char, int> charCountMap;for (char ch : input) {charCountMap[ch]++;}// 2. 将 map 转换为 vector，便于自定义排序vector<pair<char, int>> entryList(charCountMap.begin(), charCountMap.end());// 3. 自定义排序sort(entryList.begin(), entryList.end(), [](const pair<char, int>& a, const pair<char, int>& b) {// (1) 先按出现次数降序排序if (b.second != a.second) {return b.second < a.second; // 频次高的排前面}// (2) 频次相同情况下：// 小写字母优先if (islower(a.first) && isupper(b.first)) {return true;}if (isupper(a.first) && islower(b.first)) {return false;}// 同类型字符（小写或大写）按字典序升序return a.first < b.first;});// 4. 拼接结果字符串stringstream result;for (size_t i = 0; i < entryList.size(); ++i) {result << entryList[i].first << ":" << entryList[i].second;if (i != entryList.size() - 1) {result << ";";}}return result.str() + ";";
}int main() {// 读取输入字符串string input;getline(cin, input);// 输出计算结果cout << calculateFrequency(input) << endl;return 0;
}C解法
更新中
JS解法
读取用户输入的字符串 s。
使用 Map 统计各字符的出现次数：
Map 的键是字符，值是该字符的出现次数。
自定义排序
将 Map 转换为数组，使用 sort() 进行 自定义排序：
第一优先级：按出现次数降序排序（频次高的字符排前）。
第二优先级（出现次数相同时）：
若两个字符 同为小写或同为大写，按 字典序升序 排序（localeCompare()）。
若 一个大写、一个小写，小写字母排前，大写字母排后。
格式化输出
遍历排序后的数组，将字符及其出现次数拼接成 字符:次数; 格式的字符串
使用到的算法
哈希表（Map）：
用于统计字符频次，时间复杂度 O(n)（n 为字符串长度）。
Map 适用于 动态插入和查询。
自定义排序（sort() + 比较函数）：
排序优先级：
按出现次数降序（O(m log m)）。
频次相同时：
同类字符（小写/大写） 按 字典序升序（localeCompare()）。
小写字母优先，大写字母在后。
字符串拼接（map().join(‘’)）：
遍历排序数组并拼接字符串，时间复杂度 O(m)
javascript">const readline = require("readline");// 创建标准输入/输出接口
const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});// 监听标准输入，读取用户输入并计算结果
rl.on("line", (line) => {console.log(getResult(line));
});/*** 计算字符频次，并进行自定义排序后格式化输出* @param {string} s - 输入字符串* @return {string} - 频次统计后的格式化字符串*/
function getResult(s) {// 1. 统计字符频次const countMap = new Map();for (let char of s) {countMap.set(char, (countMap.get(char) || 0) + 1);}// 2. 将 Map 转换为数组，并进行排序const sortedArr = Array.from(countMap).sort((a, b) => {// (1) 先按出现次数降序排列if (a[1] !== b[1]) {return b[1] - a[1];}// (2) 频次相同时：// (2.1) 同类型字符（都小写或都大写），按字典序升序if (isSameCase(a[0], b[0])) {return a[0].localeCompare(b[0]);}// (2.2) 小写字母优先，大写字母在后return isUpper(a[0]) ? 1 : -1;});// 3. 格式化输出，拼接字符串return sortedArr.map(([char, count]) => `${char}:${count};`).join('');
}/*** 判断两个字符是否是相同类型（均为大写或均为小写）* @param {string} a - 字符1* @param {string} b - 字符2* @return {boolean} - 是否同为大小写*/
function isSameCase(a, b) {return (isUpper(a) && isUpper(b)) || (isLower(a) && isLower(b));
}/*** 判断字符是否为小写字母* @param {string} letter - 字符* @return {boolean} - 是否为小写字母*/
function isLower(letter) {return letter >= "a" && letter <= "z";
}/*** 判断字符是否为大写字母* @param {string} letter - 字符* @return {boolean} - 是否为大写字母*/
function isUpper(letter) {return letter >= "A" && letter <= "Z";
}注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
