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