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] <= 10^5
names[i] consists of lower and upper case English letters.
All the values of heights are distinct.

题意：对于每个下标 i，names[i] 和 heights[i] 表示第 i 个人的名字和身高。请按身高降序顺序返回对应的名字数组 names 。

解法1 对下标数组排序

通用做法是创建一个下标数组，对下标数组排序，这样既不会打乱输入的数组，又保证了 n a m e s [ i ] names[i] names[i] 和 h e i g h t s [ i ] heights[i] heights[i] 的对应关系。

class Solution {
public:
    vector<string> sortPeople(vector<string> &names, vector<int> &heights) {
        int n = names.size(), id[n];
        iota(id, id + n, 0);
        sort(id, id + n, [&](const auto &i, const auto &j) {
            return heights[i] > heights[j];
        });
        vector<string> ans(n);
        for (int i = 0; i < n; ++i)
            ans[i] = names[id[i]];
        return ans;
    }
};

复杂度分析：

时间复杂度： O ( n log ⁡ n ) O(n\log n) O(nlogn)
空间复杂度： O ( n ) O(n) O(n)

解法2 哈希表

由于身高各不相同，所以可以使用哈希表记录每个身高所对应的下标，最后从高到低收集对应名字即可：

class Solution {
public:
    vector<string> sortPeople(vector<string> &names, vector<int> &heights) {
        int n = names.size(), maxn = *max_element(heights.begin(), heights.end());
        int rec[maxn + 1]; memset(rec, -1, sizeof(rec));
        for (int i = 0; i < n; ++i) rec[heights[i]] = i;
        vector<string> ans;
        for (int i = maxn; i >= 1; --i)
            if (rec[i] != -1) ans.push_back(names[rec[i]]);
        return ans;
    }
};

复杂度分析：

时间复杂度： O ( m a x n ) O(maxn) O(maxn)
空间复杂度： O ( m a x n ) O(maxn) O(maxn)

memcpy0