2418.按身高排序

【LetMeFly】2418.按身高排序

力扣题目链接：https://leetcode.cn/problems/sort-the-people/

给你一个字符串数组 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 中的所有值互不相同

方法一：排序

首先，我们将 每个人的身高、姓名打包到一块，放到一个数组中。

这样，我们就能对数组以升高较高的人优先的规则排序，排序后，数组中每个人“信息对”的“姓名”信息组成一个新的数组，即为答案。

What’s More:

现在很多编程语言都自带排序功能，并且很多默认都是从小到大的规则排序的。

要么我们可以自定义排序规则，要么我们也可以采取一个小技巧，将“负的身高”作为键值排序即可。“负的身高”越小，真实身高越大。

• 时间复杂度$O(len(names)\times \log len(names))$
• 空间复杂度$O(len(names))$

AC代码

C++

class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        vector<pair<int, string>> a(names.size());
        for (int i = 0; i < names.size(); i++) {
            a[i] = {-heights[i], names[i]};
        }
        sort(a.begin(), a.end());
        vector<string> ans(a.size());
        for (int i = 0; i < a.size(); i++) {
            ans[i] = a[i].second;
        }
        return ans;
    }
};

Python

# from typing import List

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

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130373729