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
heightsare distinct.
Solution: Zip and sort
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: vector<string> sortPeople(vector<string>& names, vector<int>& heights) { vector<pair<int, string*>> data; for (int i = 0; i < names.size(); ++i) data.emplace_back(heights[i], &names[i]); sort(rbegin(data), rend(data)); vector<string> ans(names.size()); for (int i = 0; i < names.size(); ++i) ans[i].swap(*data[i].second); return ans; } }; |