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&lt;int, string&gt;&amp; a, const pair&lt;int, string&gt;&amp; b) { return a.first &gt; b.first; // 降序 }); // 3. 提取名字 vector&lt;string&gt; ans; for (auto&amp; 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&lt;int&gt; sortedHeights = heights; sort(sortedHeights.begin(), sortedHeights.end(), greater&lt;int&gt;()); // 3. 根据排序后的身高查找名字 vector&lt;string&gt; 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&lt;int&gt; 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. 按照排序后的索引顺序，将对应的名字依次加入结果数组 vector&lt;string&gt; ret; for (auto idx : index) { ret.push_back(names[idx]); } // 4. 返回按身高降序排列的名字列表 return ret; } };

4.5 流程图

5. 三种解法对比总结