題目敘述: 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
heightsare 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)
