排序應用: 身高由高到矮排列 Sort the People_Leetcode #2418

Tom Parsons on Unsplash

題目敘述: Sort the People

給定兩個輸入陣列，第一個陣列代表每個人的姓名，第二個陣列代表每個人的身高。

請依照身高從高到矮進行排列，輸出每個人的名字。

測試範例:

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

鎮列長度皆為n

• 1 <= n <= 10^3

最少一筆資料，最多一千筆資料

• 1 <= names[i].length <= 20

名字最短一個字元，最長20個字元

• 1 <= heights[i] <= 10^5

高度最矮1單位，最高十萬單位

• names[i] consists of lower and upper case English letters.

名字只會有大寫或小寫英文字母。

• All the values of heights are distinct.

每個人的身高都不相同。

演算法 照身高排序

核心資訊是身高。

先依據身高(key)和姓名(value)建立字典。

接著依照身高從高到矮排序，輸出對應的名字。

程式碼 照身高排序

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        height_dict = dict(zip(heights,names)) # // height_dict = {180: 'Mary', 165: 'John', 170: 'Emma'}
        names = []
        
        for key in sorted(height_dict.keys(),reverse=True):
            names.append(height_dict[key])
        return names

複雜度分析

時間複查度: O( n log n)

排序成本平均耗費O( n log n)

空間複雜度: O(n)

建立字典所需空間為O(n)

Reference:

[1] Sort the People - LeetCode