按身高排序

标签: 数组 哈希表 字符串 排序

难度: Easy

给你一个字符串数组 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 <= 103
  • 1 <= names[i].length <= 20
  • 1 <= heights[i] <= 105
  • names[i] 由大小写英文字母组成
  • heights 中的所有值互不相同

Submission

运行时间: 26 ms

内存: 16.4 MB

from typing import List
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        P = []
        for i in range(len(names)):
            P.append([names[i],heights[i]])
        P.sort(key = lambda item:-item[1])
        ans = []
        for p in P:
            ans.append(p[0])
        return ans

Explain

解题思路首先涉及到将名字和对应的身高组合起来，形成一个包含两个元素的列表，其中每个元素是一个包含名字和身高的小列表。接下来，使用列表的sort方法，通过自定义排序键（lambda函数），按照身高降序对这些列表进行排序。排序完成后，从排序后的列表中提取出名字，并按照身高的降序顺序将它们收集到答案列表中。

时间复杂度: O(n log n)

空间复杂度: O(n)

from typing import List
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        # 创建一个列表来存储名字和对应的身高
        P = []
        for i in range(len(names)):
            P.append([names[i], heights[i]])
        # 对列表按照身高降序排序
        P.sort(key=lambda item: -item[1])
        # 提取排序后的名字到答案列表
        ans = []
        for p in P:
            ans.append(p[0])
        return ans

Explore

在此题解中，选择将名字和身高组合成列表主要是为了方便在排序过程中同时处理这两个相关联的数据。使用列表（例如 [name, height]）的好处是它可以在需要时容易修改元素，而元组虽然更加轻量且不可变，也能达到相同的效果。使用列表或元组而不使用字典的原因是，字典不适用于此场景，因为字典是用于键值对的映射，处理单一键对应多个值时会更复杂，而且字典的遍历和排序不如列表和元组直观。

使用lambda函数通过`-item[1]`实现降序的优势在于直接性和简洁性，可以直接在排序键中指定排序的方向，而不需要在sort方法中添加额外的`reverse=True`参数。这种方法的劣势是，它仅适用于数值类型的比较，对于非数值类型的排序则不适用。使用`reverse=True`参数的优势是它更通用，可以用于任何类型的数据排序，并且使排序逻辑更明显，易于理解。

Python的sort方法默认是稳定的，这意味着如果身高数组中包含相同的身高值，那么相同身高的个体将会保持它们在原始数组中的相对顺序。因此，在本题解中若有相同的身高值，名字的顺序将会保持不变，按照它们在输入列表中的原始顺序排列。

一种更高效的方法是在排序时直接使用列表推导或生成器表达式。可以在进行排序后的步骤中直接构建答案列表，例如使用`[p[0] for p in sorted(P, key=lambda x: -x[1])]`。这样做可以减少代码行数，并且可以在一个表达式中完成排序和提取名字的操作，提高代码的简洁性和执行效率。