Description
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.length1 <= n <= 1031 <= names[i].length <= 201 <= heights[i] <= 105names[i] consists of lower and upper case English letters.- All the values of
heights are distinct.
Solutions
Solution 1: Sorting
According to the problem description, we can create an index array idx of length n, where idx[i]=i. Then we sort each index in idx in descending order according to the corresponding height in heights. Finally, we traverse each index i in the sorted idx and add names[i] to the answer array.
We can also create an array arr of length n, where each element is a tuple (heights[i], i). Then we sort arr in descending order by height. Finally, we traverse each element (heights[i], i) in the sorted arr and add names[i] to the answer array.
The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the length of the arrays names and heights.
PythonJavaC++GoTypeScriptRust
class Solution:
def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
idx = list(range(len(heights)))
idx.sort(key=lambda i: -heights[i])
return [names[i] for i in idx](code-box)
class Solution {
public String[] sortPeople(String[] names, int[] heights) {
int n = names.length;
Integer[] idx = new Integer[n];
Arrays.setAll(idx, i -> i);
Arrays.sort(idx, (i, j) -> heights[j] - heights[i]);
String[] ans = new String[n];
for (int i = 0; i < n; ++i) {
ans[i] = names[idx[i]];
}
return ans;
}
}(code-box)
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n = names.size();
vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int i, int j) { return heights[j] < heights[i]; });
vector<string> ans;
for (int i : idx) {
ans.push_back(names[i]);
}
return ans;
}
};(code-box)
func sortPeople(names []string, heights []int) (ans []string) {
n := len(names)
idx := make([]int, n)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return heights[idx[j]] < heights[idx[i]] })
for _, i := range idx {
ans = append(ans, names[i])
}
return
}(code-box)
function sortPeople(names: string[], heights: number[]): string[] {
const n = names.length;
const idx = new Array(n);
for (let i = 0; i < n; ++i) {
idx[i] = i;
}
idx.sort((i, j) => heights[j] - heights[i]);
const ans: string[] = [];
for (const i of idx) {
ans.push(names[i]);
}
return ans;
}(code-box)
impl Solution {
pub fn sort_people(names: Vec<String>, heights: Vec<i32>) -> Vec<String> {
let mut combine: Vec<(String, i32)> = names.into_iter().zip(heights.into_iter()).collect();
combine.sort_by(|a, b| b.1.cmp(&a.1));
combine.iter().map(|s| s.0.clone()).collect()
}
}(code-box)
Solution 2
PythonJavaC++GoTypeScript
class Solution:
def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
return [name for _, name in sorted(zip(heights, names), reverse=True)](code-box)
class Solution {
public String[] sortPeople(String[] names, int[] heights) {
int n = names.length;
int[][] arr = new int[n][2];
for (int i = 0; i < n; ++i) {
arr[i] = new int[] {heights[i], i};
}
Arrays.sort(arr, (a, b) -> b[0] - a[0]);
String[] ans = new String[n];
for (int i = 0; i < n; ++i) {
ans[i] = names[arr[i][1]];
}
return ans;
}
}(code-box)
class Solution {
public:
vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
int n = names.size();
vector<pair<int, int>> arr;
for (int i = 0; i < n; ++i) {
arr.emplace_back(-heights[i], i);
}
sort(arr.begin(), arr.end());
vector<string> ans;
for (int i = 0; i < n; ++i) {
ans.emplace_back(names[arr[i].second]);
}
return ans;
}
};(code-box)
func sortPeople(names []string, heights []int) []string {
n := len(names)
arr := make([][2]int, n)
for i, h := range heights {
arr[i] = [2]int{h, i}
}
sort.Slice(arr, func(i, j int) bool { return arr[i][0] > arr[j][0] })
ans := make([]string, n)
for i, x := range arr {
ans[i] = names[x[1]]
}
return ans
}(code-box)
function sortPeople(names: string[], heights: number[]): string[] {
return names
.map<[string, number]>((s, i) => [s, heights[i]])
.sort((a, b) => b[1] - a[1])
.map(([v]) => v);
}(code-box)
