LeetCode 2418：按身高排序 —— 题解
👋 欢迎阅读
🎯 欢迎来到「按身高排序」题解之旅！本文将带你从“按身高降序输出名字”这一排序需求出发，深入理解多种排序实现方式，并掌握创建二元组、哈希表映射、对下标排序三种经典技巧的适用场景。
在开始之前，建议你先：
了解题目背景：这是 LeetCode 2418 题，给定两个等长数组
names和heights（身高值互不相同），要求按身高降序返回对应的名字数组。这是一道排序与映射的入门题，但提供了多种解法思路，可灵活应用到其他类似场景。明确学习目标：掌握三种实现方式——
①创建二元组：将(身高, 名字)组合后排序，直接提取名字；
②哈希表映射：用哈希表存储<身高 -> 名字>，对身高数组排序后查表；
③对下标排序（常用技巧）：对下标数组[0, n-1]按heights降序排序，再按排好的下标取names。
理解每种方法的优劣和适用性，尤其是下标排序在避免额外空间或保持原数据不变时的通用价值。
本文将从问题转化、三种解法详解（二元组/哈希/下标排序）、代码实现到复杂度分析，层层递进。即使你对排序和映射还不熟悉，我们也会从“把身高和名字绑在一起”的直觉出发，让你轻松抓住核心思想——排序的本质是比较，但比较的对象可以是组合、映射关系或索引。现在，让我们一起按身高排好队，叫出对应名字吧！ 📏📛
一、题目
2418. 按身高排序 - 力扣（LeetCode）
二、做题思路
1. 问题分析（前置分析）
给定两个长度相等的数组：names（名字）和heights（身高，互不相同），要求按身高降序返回对应的名字数组。
核心挑战是：在排序时保持名字与身高的对应关系。
有三种常用解法：创建二元组、哈希表映射、对下标排序。
2. 解法一：创建二元组
2.1 核心思路
将每个人封装为一个二元组
(身高, 名字)，存入新数组。对二元组数组按身高降序排序。
依次提取排序后的名字，组成结果数组。
2.2 正确性说明（简单版本）
二元组将每个名字与其身高绑定在一起，排序时整体移动，不会出现错位。只要按身高降序排序，提取出的名字顺序即为题目所求。
2.3 实现细节（边界防护）
使用
vector<pair<int, string>> people存储二元组。自定义排序：按
first（身高）降序，若身高相同则按原顺序（但题目保证身高互不相同）。遍历排序后的二元组，取出
second加入结果数组。
2.4 代码
class Solution { public: vector<string> sortPeople(vector<string>& names, vector<int>& heights) { int n = names.size(); // 1. 创建二元组数组 vector<pair<int, string>> people; for (int i = 0; i < n; i++) { people.push_back({heights[i], names[i]}); } // 2. 按身高降序排序 sort(people.begin(), people.end(), [](const pair<int, string>& a, const pair<int, string>& b) { return a.first > b.first; // 降序 }); // 3. 提取名字 vector<string> ans; for (auto& p : people) { ans.push_back(p.second); } return ans; } };2.5 流程图
3. 解法二：哈希表映射
3.1 核心思路
建立哈希表
unordered_map<int, string>，将heights[i]映射到names[i]。将
heights数组降序排序。遍历排序后的
heights，用每个身高值去哈希表中查找对应的名字，依次加入结果。
3.2 正确性说明（简单版本）
因为身高值互不相同，哈希表的键唯一，所以每个身高能精确映射到唯一名字。按身高降序查找，得到的名字顺序即为目标顺序。
3.3 实现细节（边界防护）
使用
unordered_map<int, string> hash存储映射。对
heights数组进行降序排序（可用sort+ 自定义比较或greater<int>()）。遍历排序后的
heights，通过hash[height]获取对应名字。注意：哈希表查找是 O(1)，整体时间复杂度 O(n log n)，主要来自排序。
3.4 代码
class Solution { public: vector<string> sortPeople(vector<string>& names, vector<int>& heights) { int n = names.size(); // 1. 建立哈希映射 unordered_map<int, string> hash; for (int i = 0; i < n; i++) { hash[heights[i]] = names[i]; } // 2. 复制身高数组并降序排序 vector<int> sortedHeights = heights; sort(sortedHeights.begin(), sortedHeights.end(), greater<int>()); // 3. 根据排序后的身高查找名字 vector<string> ans; for (int h : sortedHeights) { ans.push_back(hash[h]); } return ans; } };3.5 流程图
4. 解法三：对下标排序（非常常用的技巧）
4.1 核心思路
创建一个下标数组
index，初始为[0, 1, 2, ..., n-1]。不移动
names和heights，而是对index进行排序，排序依据是heights[index[i]]降序。排序后，
index中的顺序即为按身高降序排列的人员索引顺序。根据
index顺序，从names中取出对应名字，组成结果数组。
4.2 正确性说明（简单版本）
通过下标作为“中介”，将排序逻辑从数据本身剥离。index排序后记录了所有下标按身高降序的排列，再通过下标访问原数组，既能得到正确顺序，又避免了原数据的移动，是一种高效且常用的技巧。
4.3 实现细节（边界防护）
初始化
index[i] = i。使用
sort(index.begin(), index.end(), [&](int a, int b){ return heights[a] > heights[b]; })。排序后，遍历
index，用names[index[i]]构造结果。此方法不需要额外存储二元组或哈希表，空间复杂度 O(n)。
4.4 代码
class Solution { public: vector<string> sortPeople(vector<string>& names, vector<int>& heights) { int n = heights.size(); // 1. 创建索引数组，初始按 0..n-1 排列，用于间接排序 vector<int> index(n); for (int i = 0; i < n; i++) { index[i] = i; } // 2. 根据身高数组对索引进行降序排序 // 自定义比较函数：索引 i 对应的人的身高如果大于索引 j 的，则 i 排在前面 sort(index.begin(), index.end(), [&](int i, int j) { return heights[i] > heights[j]; // 降序（从高到矮） }); // 3. 按照排序后的索引顺序，将对应的名字依次加入结果数组 vector<string> ret; for (auto idx : index) { ret.push_back(names[idx]); } // 4. 返回按身高降序排列的名字列表 return ret; } };4.5 流程图
5. 三种解法对比总结
| 解法 | 核心操作 | 空间复杂度 | 是否修改原数组 |
|---|---|---|---|
| 二元组 | 创建新对象排序 | O(n) | 否 |
| 哈希表 | 键值映射 + 排序 | O(n) | 是（对 heights 排序） |
| 下标排序 | 排序索引数组 | O(n) | 否（不移动原数组） |
🎯 闭幕
🎉 恭喜你完成了「按身高排序」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。
💡深入思考
题目给出了三种解法：创建二元组、使用哈希表、对下标排序。这三种方法的核心思想分别是什么？各自适用于什么场景？
解法三“对下标排序”是非常常用的技巧，它为什么能避免移动原始数据？如果要求最终输出名字数组，而不是下标，这种方法的优势体现在哪里？
如果不仅要返回名字，还要同时返回排序后的身高，上述哪种方法最容易扩展？
📚延伸挑战
将题目改为按名字的字典序排序，但需要同时输出对应的身高，你会选择哪种解法？如果名字有重复，哪种方法更稳妥？
如果你觉得本文对你有所帮助，欢迎：
👍 点赞 / 收藏
👤 关注作者，获取更多题解
💬 留言交流你的疑问或优化思路
祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨