What is the most efficient way to solve Sort the People?

Pair each name with its height, sort the pairs by height descending using array scanning and hash lookup, then extract names.

Can I sort names and heights separately?

No, sorting separately breaks the association between names and heights, leading to incorrect output.

Does this problem work with duplicate heights?

The original constraints guarantee distinct heights, so handling duplicates is unnecessary unless the variant specifies it.

What data structure ensures name-height mapping is preserved during sort?

Using tuples or pairs of (height, name) maintains the mapping and allows safe sorting by height.

How does array scanning plus hash lookup help in Sort the People?

It allows finding the tallest remaining person efficiently at each step and swapping or reordering names without losing associations.

#2418

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

按身高排序

给你一个字符串数组 names ，和一个由互不相同的正整数组成的数组 heights 。两个数组的长度均为 n 。对于每个下标 i ， names[i] 和 heights[i] 表示第 i 个人的名字和身高。请按身高降序顺序返回对应的名字数组 names 。示例 1：输入： nam…

数组哈希表字符串排序

题目描述

给你一个字符串数组 names ，和一个由 互不相同 的正整数组成的数组 heights 。两个数组的长度均为 n 。

对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。

请按身高降序顺序返回对应的名字数组 names 。

示例 1：

输入：names = ["Mary","John","Emma"], heights = [180,165,170]
输出：["Mary","Emma","John"]
解释：Mary 最高，接着是 Emma 和 John 。

示例 2：

输入：names = ["Alice","Bob","Bob"], heights = [155,185,150]
输出：["Bob","Alice","Bob"]
解释：第一个 Bob 最高，然后是 Alice 和第二个 Bob 。

提示：

n == names.length == heights.length
1 <= n <= 10³
1 <= names[i].length <= 20
1 <= heights[i] <= 10⁵
names[i] 由大小写英文字母组成
heights 中的所有值互不相同

lightbulb

解题思路

方法一：排序

根据题目描述，我们可以创建一个长度为 $n$ 的下标数组 $idx$ ，其中 $idx[i]=i$ 。然后我们对 $idx$ 中的每个下标按照 $heights$ 中对应的身高降序排序，最后遍历排序后的 $idx$ 中的每个下标 $i$ ，将 $names[i]$ 加入答案数组即可。

我们也可以创建一个长度为 $n$ 的数组 $arr$ ，数组中每个元素是一个二元组 $(heights[i], i)$ ，然后我们对 $arr$ 按照身高降序排序。最后遍历排序后的 $arr$ 中的每个元素 $(heights[i], i)$ ，将 $names[i]$ 加入答案数组即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $names$ 和 $heights$ 的长度。

1

2

3

4

5

6

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        idx = list(range(len(heights)))
        idx.sort(key=lambda i: -heights[i])
        return [names[i] for i in idx]

speed

复杂度分析

指标	值
时间	complexity is O(n \cdot \log n) due to the sorting of n elements. Space complexity is O(n) because we create an auxiliary array of tuples pairing names and heights.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Expect a direct mapping of names to heights and correct descending sort order.
question_mark
Be prepared to explain why a hash or tuple-based approach avoids mixing names and heights.
question_mark
Highlight the pattern of scanning arrays and using auxiliary structures for sorting without losing associations.

warning

常见陷阱

外企场景

error
Sorting names and heights separately without pairing can misalign names with heights.
error
Assuming heights are not distinct and trying to handle duplicates unnecessarily.
error
Forgetting to return only names in the final output instead of height-name pairs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sort by other attributes such as weight or age while keeping name mapping intact.
arrow_right_alt
Handle duplicate heights by breaking ties alphabetically or by original index.
arrow_right_alt
Sort names in ascending height order instead of descending.

help

常见问题

外企场景

继续练习

#2456 最流行的视频创作者 #2512 奖励最顶尖的 K 名学生 #2273 移除字母异位词后的结果数组