LeetCode 2418 按身高排序Sort the People三种解法全解析哈希表、配对排序与索引排序【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南围绕 LeetCode 2418「按身高排序Sort the People」展开完整拆解哈希映射Hash Map、元组配对排序Sorting the Pairs与索引排序Sorting the Indices三种思路并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust、TypeScript 十种语言的实现。读完后你将掌握在排序过程中保持两个平行数组关联关系的通用技巧以及如何根据内存开销与代码可读性挑选最合适的排序策略。该题解文章来自本仓库的 articles/sort-the-people.md遵循仓库 articles/README.md 中规定的文章规范Markdown 编写、给出时间与空间复杂度、尽量覆盖所有相关解法。问题概述给定两个长度相同的数组names人名数组和heights身高数组其中names[i]与heights[i]对应同一个人。要求返回一个按身高降序排列的人名数组。题目有一个关键约束所有身高值互不相同。这一约束直接决定了解法一哈希映射的可行性——每个身高都可以作为唯一键来反查对应的人名。在动手编码前建议先确认自己熟悉以下基础能力摘自原文档的 Prerequisites 部分哈希表Hash Maps使用键值对进行 O(1) 查找来关联数据排序算法Sorting Algorithms理解如何使用语言内置方法对数组排序自定义比较器Custom Comparators基于默认顺序以外的标准进行排序索引跟踪Index Tracking在转换过程中维护平行数组之间的关联关系。本仓库中与这些前置知识相关的文章还包括 two-integer-sum.md哈希表查找、sort-an-array.md数组排序与 top-k-elements-in-list.md基于排序的 Top-K 问题可以配套阅读。解法一哈希映射Hash Map思路Intuition由于所有身高互不相同可以把每个身高作为唯一键构建身高 → 姓名的哈希映射。随后将身高数组升序排序再从大到小遍历排序后的身高即可按顺序取出对应的人名。算法步骤Algorithm创建哈希映射将每个身高映射到对应的人名将heights数组升序排序逆序遍历排序后的身高数组即按降序访问对每个身高在哈希映射中查出人名并加入结果数组res返回包含按身高降序排列的人名的res。代码实现class Solution: def sortPeople(self, names: List[str], heights: List[int]) - List[str]: height_to_name {} for h, n in zip(heights, names): height_to_name[h] n res [] for h in reversed(sorted(heights)): res.append(height_to_name[h]) return respublic class Solution { public String[] sortPeople(String[] names, int[] heights) { MapInteger, String map new HashMap(); for (int i 0; i heights.length; i) { map.put(heights[i], names[i]); } Arrays.sort(heights); String[] res new String[heights.length]; for (int i 0; i heights.length; i) { res[i] map.get(heights[heights.length - 1 - i]); } return res; } }class Solution { public: vectorstring sortPeople(vectorstring names, vectorint heights) { unordered_mapint, string map; for (int i 0; i heights.size(); i) { map[heights[i]] names[i]; } sort(heights.begin(), heights.end()); vectorstring res; for (int i heights.size() - 1; i 0; i--) { res.push_back(map[heights[i]]); } return res; } };class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names, heights) { const map {}; for (let i 0; i heights.length; i) { map[heights[i]] names[i]; } heights.sort((a, b) a - b); const res []; for (let i heights.length - 1; i 0; i--) { res.push(map[heights[i]]); } return res; } }public class Solution { public string[] SortPeople(string[] names, int[] heights) { var map new Dictionaryint, string(); for (int i 0; i heights.Length; i) { map[heights[i]] names[i]; } Array.Sort(heights); string[] res new string[heights.Length]; for (int i 0; i heights.Length; i) { res[i] map[heights[heights.Length - 1 - i]]; } return res; } }func sortPeople(names []string, heights []int) []string { m : make(map[int]string) for i, h : range heights { m[h] names[i] } sort.Ints(heights) res : make([]string, len(heights)) for i : 0; i len(heights); i { res[i] m[heights[len(heights)-1-i]] } return res }class Solution { fun sortPeople(names: ArrayString, heights: IntArray): ArrayString { val map mutableMapOfInt, String() for (i in heights.indices) { map[heights[i]] names[i] } heights.sort() return Array(heights.size) { map[heights[heights.size - 1 - it]]!! } } }class Solution { func sortPeople(_ names: [String], _ heights: [Int]) - [String] { var map [Int: String]() for i in 0..heights.count { map[heights[i]] names[i] } let sortedHeights heights.sorted() var res [String]() for i in stride(from: heights.count - 1, through: 0, by: -1) { res.append(map[sortedHeights[i]]!) } return res } }impl Solution { pub fn sort_people(names: VecString, heights: Veci32) - VecString { let mut map HashMap::new(); for i in 0..heights.len() { map.insert(heights[i], names[i]); } let mut sorted_heights heights.clone(); sorted_heights.sort(); let mut res Vec::new(); for i in (0..sorted_heights.len()).rev() { res.push(map[sorted_heights[i]].clone()); } res } }class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names: string[], heights: number[]): string[] { const map: Recordnumber, string {}; for (let i 0; i heights.length; i) { map[heights[i]] names[i]; } heights.sort((a, b) a - b); const res: string[] []; for (let i heights.length - 1; i 0; i--) { res.push(map[heights[i]]); } return res; } }复杂度分析时间复杂度$O(n \log n)$主要来自排序哈希表的构建与查询均为 O(1)空间复杂度$O(n)$哈希映射需要存储 n 个键值对。实现细节Python 使用zip同时遍历两个数组构造映射reversed(sorted(heights))一行即可完成降序遍历Java 中注意heights是int[]基本类型数组可以直接用Arrays.sort原地排序Go 用map[int]string排序用标准库sort.IntsRust 由于所有权机制映射中暂存的是names[i]引用取值时再clone()。解法二排序配对Sorting the Pairs思路Intuition不使用哈希映射而是直接将每个身高与对应的人名组成元组。创建(height, name)配对数组后按身高降序排序关联关系在整个排序过程中始终保持完整无需额外的查找结构。算法步骤Algorithm创建配对数组每个元素为(height, name)按身高降序对配对数组排序从排序后的配对中提取所有人名构成结果数组返回结果。代码实现class Solution: def sortPeople(self, names: List[str], heights: List[int]) - List[str]: arr list(zip(heights, names)) arr.sort(reverseTrue) return [name for _, name in arr]public class Solution { public String[] sortPeople(String[] names, int[] heights) { int n names.length; Pair[] arr new Pair[n]; for (int i 0; i n; i) { arr[i] new Pair(heights[i], names[i]); } Arrays.sort(arr, (a, b) - Integer.compare(b.height, a.height)); String[] res new String[n]; for (int i 0; i n; i) { res[i] arr[i].name; } return res; } static class Pair { int height; String name; Pair(int height, String name) { this.height height; this.name name; } } }class Solution { public: vectorstring sortPeople(vectorstring names, vectorint heights) { vectorpairint, string arr; for (int i 0; i names.size(); i) { arr.emplace_back(heights[i], names[i]); } sort(arr.begin(), arr.end(), [](auto a, auto b) { return a.first b.first; }); vectorstring res; for (auto [_, name] : arr) { res.push_back(name); } return res; } };class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names, heights) { const arr names.map((name, i) [heights[i], name]); arr.sort((a, b) b[0] - a[0]); return arr.map((pair) pair[1]); } }public class Solution { public string[] SortPeople(string[] names, int[] heights) { int n names.Length; var arr new (int height, string name)[n]; for (int i 0; i n; i) { arr[i] (heights[i], names[i]); } Array.Sort(arr, (a, b) b.height.CompareTo(a.height)); string[] res new string[n]; for (int i 0; i n; i) { res[i] arr[i].name; } return res; } }func sortPeople(names []string, heights []int) []string { type pair struct { height int name string } arr : make([]pair, len(names)) for i : range names { arr[i] pair{heights[i], names[i]} } sort.Slice(arr, func(i, j int) bool { return arr[i].height arr[j].height }) res : make([]string, len(names)) for i, p : range arr { res[i] p.name } return res }class Solution { fun sortPeople(names: ArrayString, heights: IntArray): ArrayString { val arr names.indices.map { heights[it] to names[it] } .sortedByDescending { it.first } return arr.map { it.second }.toTypedArray() } }class Solution { func sortPeople(_ names: [String], _ heights: [Int]) - [String] { let arr zip(heights, names).sorted { $0.0 $1.0 } return arr.map { $0.1 } } }impl Solution { pub fn sort_people(names: VecString, heights: Veci32) - VecString { let mut arr: Vec(i32, String) heights.iter().copied() .zip(names.iter()) .collect(); arr.sort_by(|a, b| b.0.cmp(a.0)); arr.into_iter().map(|(_, name)| name.clone()).collect() } }class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names: string[], heights: number[]): string[] { const arr: [number, string][] names.map((name, i) [heights[i], name]); arr.sort((a, b) b[0] - a[0]); return arr.map((pair) pair[1]); } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$配对数组本身。实现细节Python 中zip生成的元组按字典序比较由于身高互不相同sort(reverseTrue)直接按身高降序即可C 的 lambda 比较器a.first b.first显式指定按身高降序Java 需要自建Pair类或改用int[][]/Listint[]C# 可用元组(int height, string name)Swift 的sorted是稳定排序且返回新数组因此用zip后的序列即可。解法三排序索引Sorting the Indices思路Intuition与前两种方式不同这里不复制任何数据而是构造一个索引数组再根据索引指向的身高进行排序。当人名是长字符串时这种方案在内存上更优——排序过程中只移动整数索引而不移动整个字符串。算法步骤Algorithm创建从0到n-1的索引数组使用自定义比较器按索引对应的身高降序排序索引数组将每个排序后的索引映射回对应的人名构建结果返回结果数组。代码实现class Solution: def sortPeople(self, names: List[str], heights: List[int]) - List[str]: indices list(range(len(names))) indices.sort(keylambda i: -heights[i]) return [names[i] for i in indices]public class Solution { public String[] sortPeople(String[] names, int[] heights) { Integer[] indices new Integer[names.length]; for (int i 0; i names.length; i) { indices[i] i; } Arrays.sort(indices, (i, j) - Integer.compare(heights[j], heights[i])); String[] res new String[names.length]; for (int i 0; i names.length; i) { res[i] names[indices[i]]; } return res; } }class Solution { public: vectorstring sortPeople(vectorstring names, vectorint heights) { int n names.size(); vectorint indices(n); iota(indices.begin(), indices.end(), 0); sort(indices.begin(), indices.end(), { return heights[a] heights[b]; }); vectorstring res; for (int i : indices) { res.push_back(names[i]); } return res; } };class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names, heights) { const indices names.map((_, i) i); indices.sort((a, b) heights[b] - heights[a]); return indices.map((i) names[i]); } }public class Solution { public string[] SortPeople(string[] names, int[] heights) { int[] indices new int[names.Length]; for (int i 0; i names.Length; i) { indices[i] i; } Array.Sort(indices, (i, j) heights[j].CompareTo(heights[i])); string[] res new string[names.Length]; for (int i 0; i names.Length; i) { res[i] names[indices[i]]; } return res; } }func sortPeople(names []string, heights []int) []string { n : len(names) indices : make([]int, n) for i : range indices { indices[i] i } sort.Slice(indices, func(i, j int) bool { return heights[indices[i]] heights[indices[j]] }) res : make([]string, n) for i, idx : range indices { res[i] names[idx] } return res }class Solution { fun sortPeople(names: ArrayString, heights: IntArray): ArrayString { val indices names.indices.sortedByDescending { heights[it] } return indices.map { names[it] }.toTypedArray() } }class Solution { func sortPeople(_ names: [String], _ heights: [Int]) - [String] { let indices names.indices.sorted { heights[$0] heights[$1] } return indices.map { names[$0] } } }impl Solution { pub fn sort_people(names: VecString, heights: Veci32) - VecString { let mut indices: Vecusize (0..names.len()).collect(); indices.sort_by(|a, b| heights[b].cmp(heights[a])); indices.into_iter().map(|i| names[i].clone()).collect() } }class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names: string[], heights: number[]): string[] { const indices: number[] names.map((_, i) i); indices.sort((a, b) heights[b] - heights[a]); return indices.map((i) names[i]); } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$索引数组。实现细节C 用std::iota快速生成0..n-1Java 必须使用包装类型Integer[]才能传入自定义比较器Python 的keylambda i: -heights[i]通过取负实现降序Go 在比较器中通过indices[i]间接访问身高Rust 的比较器参数解构为|a, b|以避免不必要的复制。三种解法对比与选型建议维度解法一哈希映射解法二配对排序解法三索引排序核心数据结构height → name哈希表(height, name)配对数组索引数组 自定义比较器是否依赖身高唯一是唯一键才能反查否否排序移动的对象身高数值身高 字符串整体仅整数索引长字符串场景内存开销中等额外哈希表较大整体移动字符串最小只移动整数代码可读性直观、易理解简洁多数语言一行式较绕需理解间接引用时间复杂度$O(n \log n)$$O(n \log n)$$O(n \log n)$空间复杂度$O(n)$$O(n)$$O(n)$选型建议面试首推解法一思路最自然直接利用身高唯一这一约束代码易于向面试官解释追求简洁优先解法二多数语言Python、Swift、Kotlin、TypeScript可以用极短的函数式代码完成人名很长或内存敏感时选解法三排序过程只交换整数索引避免大量字符串移动原文档也特别指出该方案在名字是长字符串时内存效率更高。常见误区Common Pitfalls误区一升序排序忘记反转题目要求按身高降序最高的人排最前返回。常见的错误是先升序排序然后忘记反转结果或调整比较器。解决方式有使用reverseTrue/reverse()/reversed(...)显式反转或直接在自定义比较器中让比较方向相反如b[0] - a[0]、b.height.CompareTo(a.height)、heights[b] heights[a]。误区二排序后丢失身高—人名关联如果只对heights排序而不同步处理names排序后你就无法知道某个身高对应谁。必须在排序前就建立关联使用哈希映射解法一在排序后通过身高反查人名或把身高与索引/人名打包成配对解法二、解法三让关联关系随排序一起移动。这也是本题考察的核心在平行数组上执行排序时如何维护元素间的对应关系。在仓库中继续学习本篇文章的原始版本articles/sort-the-people.md仓库文章写作规范articles/README.md要求每篇包含时间/空间复杂度并尽量覆盖所有解法配套前置知识文章two-integer-sum.md哈希表查找、sort-an-array.md排序问题、top-k-elements-in-list.md排序 堆的应用仓库整体结构与多语言解法总览见 README.md。将本文三种解法各写一遍并对比其运行开销是掌握排序中保持关联关系这一面试高频考点的最高效路径。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 2418 按身高排序（Sort the People）三种解法全解析：哈希表、配对排序与索引排序
LeetCode 2418 按身高排序Sort the People三种解法全解析哈希表、配对排序与索引排序【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南围绕 LeetCode 2418「按身高排序Sort the People」展开完整拆解哈希映射Hash Map、元组配对排序Sorting the Pairs与索引排序Sorting the Indices三种思路并给出 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust、TypeScript 十种语言的实现。读完后你将掌握在排序过程中保持两个平行数组关联关系的通用技巧以及如何根据内存开销与代码可读性挑选最合适的排序策略。该题解文章来自本仓库的 articles/sort-the-people.md遵循仓库 articles/README.md 中规定的文章规范Markdown 编写、给出时间与空间复杂度、尽量覆盖所有相关解法。问题概述给定两个长度相同的数组names人名数组和heights身高数组其中names[i]与heights[i]对应同一个人。要求返回一个按身高降序排列的人名数组。题目有一个关键约束所有身高值互不相同。这一约束直接决定了解法一哈希映射的可行性——每个身高都可以作为唯一键来反查对应的人名。在动手编码前建议先确认自己熟悉以下基础能力摘自原文档的 Prerequisites 部分哈希表Hash Maps使用键值对进行 O(1) 查找来关联数据排序算法Sorting Algorithms理解如何使用语言内置方法对数组排序自定义比较器Custom Comparators基于默认顺序以外的标准进行排序索引跟踪Index Tracking在转换过程中维护平行数组之间的关联关系。本仓库中与这些前置知识相关的文章还包括 two-integer-sum.md哈希表查找、sort-an-array.md数组排序与 top-k-elements-in-list.md基于排序的 Top-K 问题可以配套阅读。解法一哈希映射Hash Map思路Intuition由于所有身高互不相同可以把每个身高作为唯一键构建身高 → 姓名的哈希映射。随后将身高数组升序排序再从大到小遍历排序后的身高即可按顺序取出对应的人名。算法步骤Algorithm创建哈希映射将每个身高映射到对应的人名将heights数组升序排序逆序遍历排序后的身高数组即按降序访问对每个身高在哈希映射中查出人名并加入结果数组res返回包含按身高降序排列的人名的res。代码实现class Solution: def sortPeople(self, names: List[str], heights: List[int]) - List[str]: height_to_name {} for h, n in zip(heights, names): height_to_name[h] n res [] for h in reversed(sorted(heights)): res.append(height_to_name[h]) return respublic class Solution { public String[] sortPeople(String[] names, int[] heights) { MapInteger, String map new HashMap(); for (int i 0; i heights.length; i) { map.put(heights[i], names[i]); } Arrays.sort(heights); String[] res new String[heights.length]; for (int i 0; i heights.length; i) { res[i] map.get(heights[heights.length - 1 - i]); } return res; } }class Solution { public: vectorstring sortPeople(vectorstring names, vectorint heights) { unordered_mapint, string map; for (int i 0; i heights.size(); i) { map[heights[i]] names[i]; } sort(heights.begin(), heights.end()); vectorstring res; for (int i heights.size() - 1; i 0; i--) { res.push_back(map[heights[i]]); } return res; } };class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names, heights) { const map {}; for (let i 0; i heights.length; i) { map[heights[i]] names[i]; } heights.sort((a, b) a - b); const res []; for (let i heights.length - 1; i 0; i--) { res.push(map[heights[i]]); } return res; } }public class Solution { public string[] SortPeople(string[] names, int[] heights) { var map new Dictionaryint, string(); for (int i 0; i heights.Length; i) { map[heights[i]] names[i]; } Array.Sort(heights); string[] res new string[heights.Length]; for (int i 0; i heights.Length; i) { res[i] map[heights[heights.Length - 1 - i]]; } return res; } }func sortPeople(names []string, heights []int) []string { m : make(map[int]string) for i, h : range heights { m[h] names[i] } sort.Ints(heights) res : make([]string, len(heights)) for i : 0; i len(heights); i { res[i] m[heights[len(heights)-1-i]] } return res }class Solution { fun sortPeople(names: ArrayString, heights: IntArray): ArrayString { val map mutableMapOfInt, String() for (i in heights.indices) { map[heights[i]] names[i] } heights.sort() return Array(heights.size) { map[heights[heights.size - 1 - it]]!! } } }class Solution { func sortPeople(_ names: [String], _ heights: [Int]) - [String] { var map [Int: String]() for i in 0..heights.count { map[heights[i]] names[i] } let sortedHeights heights.sorted() var res [String]() for i in stride(from: heights.count - 1, through: 0, by: -1) { res.append(map[sortedHeights[i]]!) } return res } }impl Solution { pub fn sort_people(names: VecString, heights: Veci32) - VecString { let mut map HashMap::new(); for i in 0..heights.len() { map.insert(heights[i], names[i]); } let mut sorted_heights heights.clone(); sorted_heights.sort(); let mut res Vec::new(); for i in (0..sorted_heights.len()).rev() { res.push(map[sorted_heights[i]].clone()); } res } }class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names: string[], heights: number[]): string[] { const map: Recordnumber, string {}; for (let i 0; i heights.length; i) { map[heights[i]] names[i]; } heights.sort((a, b) a - b); const res: string[] []; for (let i heights.length - 1; i 0; i--) { res.push(map[heights[i]]); } return res; } }复杂度分析时间复杂度$O(n \log n)$主要来自排序哈希表的构建与查询均为 O(1)空间复杂度$O(n)$哈希映射需要存储 n 个键值对。实现细节Python 使用zip同时遍历两个数组构造映射reversed(sorted(heights))一行即可完成降序遍历Java 中注意heights是int[]基本类型数组可以直接用Arrays.sort原地排序Go 用map[int]string排序用标准库sort.IntsRust 由于所有权机制映射中暂存的是names[i]引用取值时再clone()。解法二排序配对Sorting the Pairs思路Intuition不使用哈希映射而是直接将每个身高与对应的人名组成元组。创建(height, name)配对数组后按身高降序排序关联关系在整个排序过程中始终保持完整无需额外的查找结构。算法步骤Algorithm创建配对数组每个元素为(height, name)按身高降序对配对数组排序从排序后的配对中提取所有人名构成结果数组返回结果。代码实现class Solution: def sortPeople(self, names: List[str], heights: List[int]) - List[str]: arr list(zip(heights, names)) arr.sort(reverseTrue) return [name for _, name in arr]public class Solution { public String[] sortPeople(String[] names, int[] heights) { int n names.length; Pair[] arr new Pair[n]; for (int i 0; i n; i) { arr[i] new Pair(heights[i], names[i]); } Arrays.sort(arr, (a, b) - Integer.compare(b.height, a.height)); String[] res new String[n]; for (int i 0; i n; i) { res[i] arr[i].name; } return res; } static class Pair { int height; String name; Pair(int height, String name) { this.height height; this.name name; } } }class Solution { public: vectorstring sortPeople(vectorstring names, vectorint heights) { vectorpairint, string arr; for (int i 0; i names.size(); i) { arr.emplace_back(heights[i], names[i]); } sort(arr.begin(), arr.end(), [](auto a, auto b) { return a.first b.first; }); vectorstring res; for (auto [_, name] : arr) { res.push_back(name); } return res; } };class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names, heights) { const arr names.map((name, i) [heights[i], name]); arr.sort((a, b) b[0] - a[0]); return arr.map((pair) pair[1]); } }public class Solution { public string[] SortPeople(string[] names, int[] heights) { int n names.Length; var arr new (int height, string name)[n]; for (int i 0; i n; i) { arr[i] (heights[i], names[i]); } Array.Sort(arr, (a, b) b.height.CompareTo(a.height)); string[] res new string[n]; for (int i 0; i n; i) { res[i] arr[i].name; } return res; } }func sortPeople(names []string, heights []int) []string { type pair struct { height int name string } arr : make([]pair, len(names)) for i : range names { arr[i] pair{heights[i], names[i]} } sort.Slice(arr, func(i, j int) bool { return arr[i].height arr[j].height }) res : make([]string, len(names)) for i, p : range arr { res[i] p.name } return res }class Solution { fun sortPeople(names: ArrayString, heights: IntArray): ArrayString { val arr names.indices.map { heights[it] to names[it] } .sortedByDescending { it.first } return arr.map { it.second }.toTypedArray() } }class Solution { func sortPeople(_ names: [String], _ heights: [Int]) - [String] { let arr zip(heights, names).sorted { $0.0 $1.0 } return arr.map { $0.1 } } }impl Solution { pub fn sort_people(names: VecString, heights: Veci32) - VecString { let mut arr: Vec(i32, String) heights.iter().copied() .zip(names.iter()) .collect(); arr.sort_by(|a, b| b.0.cmp(a.0)); arr.into_iter().map(|(_, name)| name.clone()).collect() } }class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names: string[], heights: number[]): string[] { const arr: [number, string][] names.map((name, i) [heights[i], name]); arr.sort((a, b) b[0] - a[0]); return arr.map((pair) pair[1]); } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$配对数组本身。实现细节Python 中zip生成的元组按字典序比较由于身高互不相同sort(reverseTrue)直接按身高降序即可C 的 lambda 比较器a.first b.first显式指定按身高降序Java 需要自建Pair类或改用int[][]/Listint[]C# 可用元组(int height, string name)Swift 的sorted是稳定排序且返回新数组因此用zip后的序列即可。解法三排序索引Sorting the Indices思路Intuition与前两种方式不同这里不复制任何数据而是构造一个索引数组再根据索引指向的身高进行排序。当人名是长字符串时这种方案在内存上更优——排序过程中只移动整数索引而不移动整个字符串。算法步骤Algorithm创建从0到n-1的索引数组使用自定义比较器按索引对应的身高降序排序索引数组将每个排序后的索引映射回对应的人名构建结果返回结果数组。代码实现class Solution: def sortPeople(self, names: List[str], heights: List[int]) - List[str]: indices list(range(len(names))) indices.sort(keylambda i: -heights[i]) return [names[i] for i in indices]public class Solution { public String[] sortPeople(String[] names, int[] heights) { Integer[] indices new Integer[names.length]; for (int i 0; i names.length; i) { indices[i] i; } Arrays.sort(indices, (i, j) - Integer.compare(heights[j], heights[i])); String[] res new String[names.length]; for (int i 0; i names.length; i) { res[i] names[indices[i]]; } return res; } }class Solution { public: vectorstring sortPeople(vectorstring names, vectorint heights) { int n names.size(); vectorint indices(n); iota(indices.begin(), indices.end(), 0); sort(indices.begin(), indices.end(), { return heights[a] heights[b]; }); vectorstring res; for (int i : indices) { res.push_back(names[i]); } return res; } };class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names, heights) { const indices names.map((_, i) i); indices.sort((a, b) heights[b] - heights[a]); return indices.map((i) names[i]); } }public class Solution { public string[] SortPeople(string[] names, int[] heights) { int[] indices new int[names.Length]; for (int i 0; i names.Length; i) { indices[i] i; } Array.Sort(indices, (i, j) heights[j].CompareTo(heights[i])); string[] res new string[names.Length]; for (int i 0; i names.Length; i) { res[i] names[indices[i]]; } return res; } }func sortPeople(names []string, heights []int) []string { n : len(names) indices : make([]int, n) for i : range indices { indices[i] i } sort.Slice(indices, func(i, j int) bool { return heights[indices[i]] heights[indices[j]] }) res : make([]string, n) for i, idx : range indices { res[i] names[idx] } return res }class Solution { fun sortPeople(names: ArrayString, heights: IntArray): ArrayString { val indices names.indices.sortedByDescending { heights[it] } return indices.map { names[it] }.toTypedArray() } }class Solution { func sortPeople(_ names: [String], _ heights: [Int]) - [String] { let indices names.indices.sorted { heights[$0] heights[$1] } return indices.map { names[$0] } } }impl Solution { pub fn sort_people(names: VecString, heights: Veci32) - VecString { let mut indices: Vecusize (0..names.len()).collect(); indices.sort_by(|a, b| heights[b].cmp(heights[a])); indices.into_iter().map(|i| names[i].clone()).collect() } }class Solution { /** * param {string[]} names * param {number[]} heights * return {string[]} */ sortPeople(names: string[], heights: number[]): string[] { const indices: number[] names.map((_, i) i); indices.sort((a, b) heights[b] - heights[a]); return indices.map((i) names[i]); } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(n)$索引数组。实现细节C 用std::iota快速生成0..n-1Java 必须使用包装类型Integer[]才能传入自定义比较器Python 的keylambda i: -heights[i]通过取负实现降序Go 在比较器中通过indices[i]间接访问身高Rust 的比较器参数解构为|a, b|以避免不必要的复制。三种解法对比与选型建议维度解法一哈希映射解法二配对排序解法三索引排序核心数据结构height → name哈希表(height, name)配对数组索引数组 自定义比较器是否依赖身高唯一是唯一键才能反查否否排序移动的对象身高数值身高 字符串整体仅整数索引长字符串场景内存开销中等额外哈希表较大整体移动字符串最小只移动整数代码可读性直观、易理解简洁多数语言一行式较绕需理解间接引用时间复杂度$O(n \log n)$$O(n \log n)$$O(n \log n)$空间复杂度$O(n)$$O(n)$$O(n)$选型建议面试首推解法一思路最自然直接利用身高唯一这一约束代码易于向面试官解释追求简洁优先解法二多数语言Python、Swift、Kotlin、TypeScript可以用极短的函数式代码完成人名很长或内存敏感时选解法三排序过程只交换整数索引避免大量字符串移动原文档也特别指出该方案在名字是长字符串时内存效率更高。常见误区Common Pitfalls误区一升序排序忘记反转题目要求按身高降序最高的人排最前返回。常见的错误是先升序排序然后忘记反转结果或调整比较器。解决方式有使用reverseTrue/reverse()/reversed(...)显式反转或直接在自定义比较器中让比较方向相反如b[0] - a[0]、b.height.CompareTo(a.height)、heights[b] heights[a]。误区二排序后丢失身高—人名关联如果只对heights排序而不同步处理names排序后你就无法知道某个身高对应谁。必须在排序前就建立关联使用哈希映射解法一在排序后通过身高反查人名或把身高与索引/人名打包成配对解法二、解法三让关联关系随排序一起移动。这也是本题考察的核心在平行数组上执行排序时如何维护元素间的对应关系。在仓库中继续学习本篇文章的原始版本articles/sort-the-people.md仓库文章写作规范articles/README.md要求每篇包含时间/空间复杂度并尽量覆盖所有解法配套前置知识文章two-integer-sum.md哈希表查找、sort-an-array.md排序问题、top-k-elements-in-list.md排序 堆的应用仓库整体结构与多语言解法总览见 README.md。将本文三种解法各写一遍并对比其运行开销是掌握排序中保持关联关系这一面试高频考点的最高效路径。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考