🔗 🟢 2418. Sort the People 1193

tags: Weekly Contest 312 陣列(Array) 字串(String) 排序(Sort) 雜湊表(Hash Table)

題意

給定一個字串陣列 namesnames 和一個由 不同的 正整陣列成的 heightsheights 陣列。這兩個陣列的長度都是 nn。

對於每一個下標 ii ，names[i]names[i] 和 heights[i]heights[i] 分別代表第 ii 個人的名字和身高。

請根據人們的身高，降序排列 namesnames。

思路：對下標陣列排序

一個比較簡單的做法是將 namesnames 和 heightsheights 兩個陣列合併成一個二維陣列，然後此二維陣列中的身高降序排序，最後取出排序後的名字即可。在 python 中可以使用 zip 函數來實現，並且可以在一行程式碼中完成。

另外一個比較通用的做法是創建一個下標陣列 idsids，然後根據 heightsheights 陣列對 idsids 陣列進行排序。最後根據排序好的下標陣列，生成排序後的名字列表做為答案。

具體步驟如下：

  1. 首先，創建一個與 namesnames 和 heightsheights 相同長度的下標陣列 idsids，這個陣列的元素是 0 到 n−1n-1 的數字。
  2. 使用這個下標陣列來排序，排序的依據是 heightsheights 中對應的值。我們使用 lambda 函數來定義排序的依據，即對於下標 xx 和 yy，如果 heights[x]>heights[y]heights[x] > heights[y] 則 xx 排在 yy 前面。
  3. 創建一個答案陣列 ansans，遍歷排序好的下標陣列，將對應的名字加入答案陣列中。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，其中 nn 是 namesnames 的長度。
  • 空間複雜度：O(n)\mathcal{O}(n)，需要額外的空間來存儲下標陣列。
1
2
3
4
5
6
7
class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        # return [name for _, name in sorted(zip(heights, names), reverse=True)]
        n = len(names)
        ids = [i for i in range(n)]
        ids.sort(key=lambda x: heights[x], reverse=True)
        return [names[i] for i in ids]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<int> ids(n);
        iota(ids.begin(), ids.end(), 0);
        sort(ids.begin(), ids.end(), [&](int a, int b) {
            return heights[a] > heights[b];
        });
        vector<string> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = names[ids[i]];
        }
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality,extremely detailed CG unity 8k wallpaper, HDR, High Detail,
1girl, solo, long hair, bangs, brown hair, shirt, long sleeves, dress, white shirt, outdoors, day, white dress, blurry, from side, tree, lips, looking up, building, photo background