JZTXT

[LeetCode] 2418. Sort the People

发布时间 2023-04-25 23:41:40作者: CNoodle

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实现

 1 class Solution {
 2     public String[] sortPeople(String[] names, int[] heights) {
 3         HashMap<Integer, String> map = new HashMap<>();
 4         int n = heights.length;
 5         for (int i = 0; i < n; i++) {
 6             map.put(heights[i], names[i]);
 7         }
 8         
 9         Arrays.sort(heights);
10         String[] res = new String[n];
11         int index = 0;
12         for (int i = heights.length - 1; i >= 0; i--) {
13             res[index++] = map.get(heights[i]);
14         }
15         return res;
16     }
17 }

 

LeetCode 题目总结