Easy

题目描述

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

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

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

示例 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 中的所有值互不相同

解题思路

这道题需要根据身高对人名进行排序，有多种解决思路：

方法一：配对排序（推荐） 将姓名和身高配对，然后按身高降序排序。可以使用数组下标作为中介，或者直接将姓名和身高配对存储。

方法二：选择排序 按照题目提示，找到最高的人与第一位交换，找到第二高的人与第二位交换，以此类推。这是一种直接的选择排序思路。

方法三：哈希表映射 使用哈希表建立身高到姓名的映射，然后对身高数组排序，最后根据排序结果查表得到对应姓名。

其中配对排序是最常用且效率较高的方法。我们创建一个索引数组，根据身高对索引进行排序，然后按排序后的索引顺序提取姓名。这样既保持了代码简洁，又避免了额外的空间开销。

代码实现

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

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

public class Solution {
    public string[] SortPeople(string[] names, int[] heights) {
        int n = names.Length;
        int[] indices = new int[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        
        Array.Sort(indices, (a, b) => heights[b].CompareTo(heights[a]));
        
        string[] result = new string[n];
        for (int i = 0; i < n; i++) {
            result[i] = names[indices[i]];
        }
        
        return result;
    }
}

var sortPeople = function(names, heights) {
    const indices = Array.from({length: names.length}, (_, i) => i);
    indices.sort((a, b) => heights[b] - heights[a]);
    return indices.map(i => names[i]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序操作上
空间复杂度O(n)需要额外的索引数组和结果数组

相关题目