[LeetCode] 2418. Sort the People

You are given an array of strings names, and an array heights that consists of distinct positive integers. Both arrays are of length n.

For each index i, names[i] and heights[i] denote the name and height of the ith person.

Return names sorted in descending order by the people’s heights.

Example 1:
Input: names = [“Mary”,”John”,”Emma”], heights = [180,165,170]
Output: [“Mary”,”Emma”,”John”]
Explanation: Mary is the tallest, followed by Emma and John.

Example 2:
Input: names = [“Alice”,”Bob”,”Bob”], heights = [155,185,150]
Output: [“Bob”,”Alice”,”Bob”]
Explanation: The first Bob is the tallest, followed by Alice and the second Bob.

Constraints:
n == names.length == heights.length
1 <= n <= 103
1 <= names[i].length <= 20
1 <= heights[i] <= 105
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

按身高排序。

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-the-people
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

思路是排序。注意题目说了每个人的身高是独一无二的，所以这里我们可以用一个 hashmap 存每个人的<身高，名字>。然后我们对 heights 数组进行排序并从大到小遍历。遍历的时候将每个身高在 hashmap 中对应的名字放入结果集。

这道题如果难一点，可以把条件改为如果身高不是独一无二的话该怎么做。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        HashMap<Integer, String> map = new HashMap<>();
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            map.put(heights[i], names[i]);
        }

        Arrays.sort(heights);
        String[] res = new String[n];
        int index = 0;
        for (int i = heights.length - 1; i >= 0; i--) {
            res[index++] = map.get(heights[i]);
        }
        return res;
    }
}