LeetCode 791 自定义排序字符串：从比较器排序到 O(n) 计数重构的双解法精讲（leetcode 仓库实战）

LeetCode 791 自定义排序字符串：从比较器排序到 O(n) 计数重构的双解法精讲（leetcode 仓库实战）

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文以 leetcode 仓库中的 custom-sort-string.md 为核心，完整覆盖 LeetCode 791「Custom Sort String（自定义排序字符串）」的两种解法——自定义比较器排序与字符频率计数，继承原文档全部直觉分析、算法步骤、九语言代码与复杂度结论，并结合仓库内 Python 解 与 Java 解 的源码实现展开纵深讲解。读完后你能够掌握：如何用「排名映射 + 自定义排序」处理任意偏序需求，以及如何用「频率计数 + 按序输出」将问题从 O(n log n) 优化到 O(n)，并避开原文档总结的三类常见陷阱。

问题背景与前置知识

题目要求：给定字符串order（其字符按任意排列）与字符串s，重排s使得其中出现过的字符按照order中出现的相对顺序排列；s中未出现在order里的字符可以放在任意位置。仓库文档在 custom-sort-string.md 的 "Prerequisites" 一节中明确列出了解题所需的三项前置能力：

• 哈希映射（Hash Maps）：用字典把字符映射到它在order中的排名或优先级；
• 自定义排序 / 比较器（Custom Sorting / Comparators）：定义基于非标准准则的比较函数来排序元素；
• 频率计数（Frequency Counting）：统计字符出现次数，以便按特定顺序重构字符串。

这两项能力恰好对应文档给出的两条解法路线：前者走「比较器排序」，后者走「计数重构」。

解法一：自定义比较器（Custom Comparator）

核心直觉

目标是让s中的字符按照它们在order中的相对顺序出现。文档给出的关键洞察是：可以依据字符在order中的位置给每个字符分配一个「排名（rank）」。对于不在order中的字符，赋予一个较高排名（如26），使其自然落在结果末尾。用这些排名作为排序键对s排序后，字符便自动按自定义顺序排列。

算法步骤

原文档将算法归纳为四步，这里完整保留：

1. 构建排名映射rank：order中每个字符映射到其下标（0,1,2, ...）；
2. 不在order中的字符使用默认排名26（高于order中任何位置）；
3. 以 rank 值为键对s的字符执行排序；
4. 将排序后的字符拼接回字符串返回。

多语言实现

以下代码完整继承自 custom-sort-string.md 解法一的多语言实现，涵盖 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言。

Python 版是最精炼的形态——排名字典推导式加一行带默认值的rank.get排序键：

class Solution: def customSortString(self, order: str, s: str) -> str: rank = {c: i for i, c in enumerate(order)} return ''.join(sorted(s, key=lambda c: rank.get(c, 26)))

注意rank.get(c, 26)中的26即默认排名，对应后文「常见陷阱」中"缺失字符排名赋值错误"一节：order长度为n，合法排名最大为n - 1，而题目保证字符范围是 26 个小写字母，因此26保证严格大于任何合法排名。

Java 版用长度为 26 的int数组存排名，并用装箱的Character[]承载比较器（Arrays.sort对基本类型无法接受Comparator）：

public class Solution { public String customSortString(String order, String s) { int[] rank = new int[26]; for (int i = 0; i < order.length(); i++) { rank[order.charAt(i) - 'a'] = i + 1; } Character[] arr = new Character[s.length()]; for (int i = 0; i < s.length(); i++) { arr[i] = s.charAt(i); } Arrays.sort(arr, (a, b) -> rank[a - 'a'] - rank[b - 'a']); StringBuilder sb = new StringBuilder(); for (char c : arr) { sb.append(c); } return sb.toString(); } }

这里的细节值得注意：Java 版把排名设为i + 1而非i，于是「不在 order 中的字符」排名为 0（int[]初始值），天然排在所有已排名字符之后，省去了显式默认值；而 C++ 版则相反，先用26填满 rank 数组再覆盖，两种写法殊途同归。

C++ 版直接对string原地排序，用 lambda 捕获 rank 向量：

class Solution { public: string customSortString(string order, string s) { vector<int> rank(26, 26); for (int i = 0; i < order.size(); ++i) { rank[order[i] - 'a'] = i; } sort(s.begin(), s.end(), & { return rank[a - 'a'] < rank[b - 'a']; }); return s; } };

JavaScript 版借助??空值合并运算符处理默认排名：

class Solution { customSortString(order, s) { const rank = {}; for (let i = 0; i < order.length; i++) { rank[order[i]] = i; } return [...s] .sort((a, b) => { const ra = rank[a] ?? 26; const rb = rank[b] ?? 26; return ra - rb; }) .join(''); } }

C# 版用Dictionary<char, int>并在比较器里做ContainsKey判断：

public class Solution { public string CustomSortString(string order, string s) { Dictionary<char, int> rank = new Dictionary<char, int>(); for (int i = 0; i < order.Length; i++) { rank[order[i]] = i; } char[] arr = s.ToCharArray(); Array.Sort(arr, (a, b) => { int ra = rank.ContainsKey(a) ? rank[a] : 26; int rb = rank.ContainsKey(b) ? rank[b] : 26; return ra - rb; }); return new string(arr); } }

Go 版用map[byte]int配sort.Slice，双返回值查询显式处理缺省键：

func customSortString(order string, s string) string { rank := make(map[byte]int) for i := 0; i < len(order); i++ { rank[order[i]] = i } arr := []byte(s) sort.Slice(arr, func(i, j int) bool { ri, oki := rank[arr[i]] rj, okj := rank[arr[j]] if !oki { ri = 26 } if !okj { rj = 26 } return ri < rj }) return string(arr) }

Kotlin 版与 Swift 版风格简洁，分别用getOrDefault与default:子句表达默认排名：

class Solution { fun customSortString(order: String, s: String): String { val rank = mutableMapOf<Char, Int>() for (i in order.indices) { rank[order[i]] = i } return s.toCharArray() .sortedBy { rank.getOrDefault(it, 26) } .joinToString("") } }

class Solution { func customSortString(_ order: String, _ s: String) -> String { var rank = [Character: Int]() for (i, c) in order.enumerated() { rank[c] = i } return String(s.sorted { rank[$0, default: 26] < rank[$1, default: 26] }) } }

Rust 版同样采用固定大小的[26i32; 26]排名数组（未初始化为 26，这里依赖order与s中缺失字符排名为 0 排在末尾——注意这与文档其他语言的"缺失字符默认 26"语义相反，但仅当order恰好覆盖所有字符时才可能冲突，题目下两种约定均满足"未排名字符在 order 字符之后或任意位置"的宽松要求；从源码结构看，仓库该实现以"缺省排名 0 排最前"运行，读者迁移此代码时应自行确认约定）配sort_by_key：

impl Solution { pub fn custom_sort_string(order: String, s: String) -> String { let mut rank = [26i32; 26]; for (i, c) in order.bytes().enumerate() { rank[(c - b'a') as usize] = i as i32; } let mut arr: Vec<u8> = s.into_bytes(); arr.sort_by_key(|&c| rank[(c - b'a') as usize]); String::from_utf8(arr).unwrap() } }

复杂度分析

原文档给出的结论：

• 时间复杂度：O(n log n)，其中 n 为s的长度（排序主导）；
• 空间复杂度：O(1) 或 O(n)，取决于具体排序实现与语言对字符串不可变性/装箱的开销（如 Java 需额外Character[]数组，C++ 原地排序则额外空间几乎为常数）。

解法二：频率计数（Frequency Count）—— O(n) 直接重构

核心直觉

文档第二节的洞察是：既然已经知道目标顺序，就不必"排序"，而是直接按序构造结果。先用计数数组统计s中每个字符的出现次数；然后沿order遍历，把每个字符按其计数追加到结果中；最后再沿整个字母表把order中未出现的剩余字符补齐。整个过程无需任何比较，规避了 O(n log n) 的排序开销。

算法步骤

1. 创建长度为 26 的频率数组，统计s中每个小写字母的出现次数；
2. 遍历order中每个字符，将其按剩余计数追加到结果，同时递减计数直至耗尽；
3. 遍历全部 26 个字母，把仍未耗尽计数的字符（即s有而order无的字符）按字母序追加到结果末尾；
4. 返回拼接完成的结果字符串。

多语言实现

以下代码完整继承自 custom-sort-string.md 解法二。

Python 版：

class Solution: def customSortString(self, order: str, s: str) -> str: count = [0] * 26 for c in s: count[ord(c) - ord('a')] += 1 res = [] for c in order: idx = ord(c) - ord('a') while count[idx]: res.append(c) count[idx] -= 1 for idx in range(26): c = chr(ord('a') + idx) while count[idx]: count[idx] -= 1 res.append(c) return ''.join(res)

Java 版：

public class Solution { public String customSortString(String order, String s) { int[] count = new int[26]; for (char c : s.toCharArray()) { count[c - 'a']++; } StringBuilder res = new StringBuilder(); for (char c : order.toCharArray()) { int idx = c - 'a'; while (count[idx] > 0) { res.append(c); count[idx]--; } } for (int idx = 0; idx < 26; idx++) { char c = (char) ('a' + idx); while (count[idx] > 0) { res.append(c); count[idx]--; } } return res.toString(); } }

C++ 版：

class Solution { public: string customSortString(string order, string s) { vector<int> count(26, 0); for (char c : s) { count[c - 'a']++; } string res; for (char c : order) { int idx = c - 'a'; while (count[idx] > 0) { res += c; count[idx]--; } } for (int idx = 0; idx < 26; ++idx) { char c = 'a' + idx; while (count[idx] > 0) { res += c; count[idx]--; } } return res; } };

JavaScript 版：

class Solution { customSortString(order, s) { const count = new Array(26).fill(0); for (let c of s) { count[c.charCodeAt(0) - 97]++; } const res = []; for (let c of order) { let idx = c.charCodeAt(0) - 97; while (count[idx] > 0) { res.push(c); count[idx]--; } } for (let idx = 0; idx < 26; idx++) { let c = String.fromCharCode(97 + idx); while (count[idx] > 0) { res.push(c); count[idx]--; } } return res.join(''); } }

C# 版：

public class Solution { public string CustomSortString(string order, string s) { int[] count = new int[26]; foreach (char c in s) { count[c - 'a']++; } StringBuilder res = new StringBuilder(); foreach (char c in order) { int idx = c - 'a'; while (count[idx] > 0) { res.Append(c); count[idx]--; } } for (int idx = 0; idx < 26; idx++) { char c = (char)('a' + idx); while (count[idx] > 0) { res.Append(c); count[idx]--; } } return res.ToString(); } }

Go 版：

func customSortString(order string, s string) string { count := make([]int, 26) for i := 0; i < len(s); i++ { count[s[i]-'a']++ } var res []byte for i := 0; i < len(order); i++ { idx := order[i] - 'a' for count[idx] > 0 { res = append(res, order[i]) count[idx]-- } } for idx := 0; idx < 26; idx++ { c := byte('a' + idx) for count[idx] > 0 { res = append(res, c) count[idx]-- } } return string(res) }

Kotlin 版：

class Solution { fun customSortString(order: String, s: String): String { val count = IntArray(26) for (c in s) { count[c - 'a']++ } val res = StringBuilder() for (c in order) { val idx = c - 'a' while (count[idx] > 0) { res.append(c) count[idx]-- } } for (idx in 0 until 26) { val c = ('a' + idx) while (count[idx] > 0) { res.append(c) count[idx]-- } } return res.toString() } }

Swift 版：

class Solution { func customSortString(_ order: String, _ s: String) -> String { var count = Int for c in s { count[Int(c.asciiValue! - Character("a").asciiValue!)] += 1 } var res = "" for c in order { let idx = Int(c.asciiValue! - Character("a").asciiValue!) while count[idx] > 0 { res.append(c) count[idx] -= 1 } } for idx in 0..<26 { let c = Character(UnicodeScalar(Int(Character("a").asciiValue!) + idx)!) while count[idx] > 0 { res.append(c) count[idx] -= 1 } } return res } }

Rust 版：

impl Solution { pub fn custom_sort_string(order: String, s: String) -> String { let mut count = [0i32; 26]; for c in s.bytes() { count[(c - b'a') as usize] += 1; } let mut res = String::new(); for c in order.bytes() { let idx = (c - b'a') as usize; while count[idx] > 0 { res.push(c as char); count[idx] -= 1; } } for idx in 0..26 { let c = (b'a' + idx as u8) as char; while count[idx] > 0 { res.push(c); count[idx] -= 1; } } res } }

复杂度分析

原文档结论：

• 时间复杂度：O(n)。三趟线性扫描（计数、按order输出、补齐剩余字母）总工作量为 O(n + 26)；
• 空间复杂度：O(n)。计数数组是 O(1)（固定 26），但结果字符串本身占 O(n)。

仓库源码印证：官方提交代码的「哈希表计数」变体

除文档中的 26 位定长计数数组写法外，leetcode 仓库中本题的两份正式提交实现走了另一条等价路线——用哈希表计数、沿 order 消费、再遍历哈希表剩余项补齐：

python/0791-custom-sort-string.py 的实现：

class Solution: def customSortString(self, order: str, s: str) -> str: char_count_of_s = {} for i in s: char_count_of_s[i] = char_count_of_s.get(i, 0) + 1 satisfied_string = "" for char in order: if char in char_count_of_s: satisfied_string += char * char_count_of_s[char] del char_count_of_s[char] for key,val in char_count_of_s.items(): satisfied_string += key * val return satisfied_string

与文档解法二的差异在于：计数容器从定长数组换成字典，「补齐剩余字符」一步不再依赖字母序遍历 26 个位置，而是直接遍历字典剩余键。由于题目允许剩余字符任意排列，这一变体在正确性上与文档解法等价；从源码结构看，这种写法对"字符集不限于 26 个小写字母"的场景更具扩展性。

java/0791-custom-sort-string.java 则展示了同一思路在 Java 中的形态——用HashMap<Character, Integer>计数，沿order循环消费计数，最后遍历keySet()补齐：

class Solution { public String customSortString(String order, String s) { Map<Character, Integer> map = new HashMap<>(); for(char c: s.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1); StringBuilder res = new StringBuilder(); for(char c: order.toCharArray()){ while(map.containsKey(c) && map.get(c) > 0){ res.append(c); map.put(c, map.get(c)-1); } } for(char c: map.keySet()){ while(map.get(c) > 0){ res.append(c); map.put(c, map.get(c)-1); } } return res.toString(); } }

对照文档与仓库源码可以看到一个清晰的实现光谱：比较器排序法（O(n log n)，代码最简）→ 定长 26 位计数法（O(n)，依赖"仅小写字母"的题设）→ 哈希表计数法（O(n)，字符集无关，剩余字符顺序不保证）。三者互为印证，可按语言特性与场景约束灵活选用。

常见陷阱（Common Pitfalls）

原文档 "Common Pitfalls" 一节总结了三个高频错误，这里完整继承并加以展开。

陷阱一：丢失 order 中不存在的字符

s中未出现在order里的字符必须出现在结果中，只按order输出会产生长度不足的错误结果。文档给出的正误对照：

# Wrong: only includes characters from order for c in order: res += c * count[c] # Missing: characters in s but not in order are lost # Correct: also append remaining characters for c in order: res += c * count[ord(c) - ord('a')] count[ord(c) - ord('a')] = 0 for i in range(26): res += chr(ord('a') + i) * count[i] # Append leftovers

正确做法的核心是"消费即清零"：每个order字符输出后置零其计数，随后用一整个字母表扫描兜底。仓库 Python 提交 中的del char_count_of_s[char]与文档"消费后清零"是同一语义的两种表达——前者删除键、后者置零值，目的都是让剩余字符只被输出一次。

陷阱二：依赖不稳定排序来保持相对顺序

使用比较排序时，排名相同的字符（典型即"都不在 order 里"的字符）之间的相对顺序可能被打乱。文档指出：虽然按题意这类打乱在技术上合法，但容易造成理解混乱；计数法则完全规避此问题，因为它是"按序构造"而非"重排"。另外从语言实现看，Python 的sorted与 C# 的Array.Sort（对对象数组）稳定性表现各异，跨语言比较器代码时不应假设同排名元素顺序不变。

陷阱三：缺失字符的排名赋值错误

不在order中的字符需要一个高于所有合法位置的默认排名。忘记提供默认值，或用一个与合法位置冲突的排名，都会导致错误排序甚至运行时异常。文档给出的正误对照：

# Wrong: no default rank, causes KeyError rank = {c: i for i, c in enumerate(order)} sorted(s, key=lambda c: rank[c]) # Crashes if c not in order # Correct: provide default rank sorted(s, key=lambda c: rank.get(c, 26))

各语言的对应防御手段分别是：Python 的dict.get(c, 26)、JavaScript 的?? 26、C# 的ContainsKey三元判断、Go 的 map 双返回值查询、Kotlin 的getOrDefault、Swift 的下标default:。

两种解法对比与选型建议

选型建议：面试白板优先写比较器排序法，展示"排名映射"这一通用技巧；追求最优复杂度或对大数据量敏感时切到频率计数法；若题目扩展到非 26 字母字符集（如任意 Unicode），直接采用仓库 Java 提交 展示的哈希表计数变体。

小结

本文完整覆盖了 leetcode 仓库文档 custom-sort-string.md 的全部技术内容：三项前置知识、自定义比较器解法的四步算法与九语言实现、频率计数解法的 O(n) 重构策略、三组复杂度结论，以及"丢失剩余字符 / 不稳定排序 / 默认排名缺失"三大陷阱。结合仓库内 Python 与 Java 提交代码 的哈希表变体，可以看出"排名映射 + 排序"与"计数 + 按序输出"两条主线在实现上的完整光谱，可作为后续处理任意"自定义顺序重排"类问题（如带偏序约束的字符串/数组重排）的直接模板。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode