題目描述與示例

題目描述

某學校舉行運動會,學生們按編號(1、2、3.....n) 進行標識,

現需要按照身高由低到高排列，對身高相同的人，按體重由輕到重排列，對于身高體重都相同的人，維持原有的編號順序關系。

請輸出排列后的學生編號

輸入描述

兩個序列，每個序列由 n 個正整數組成(0 < n < 100)。第一個序列中的數值代表身高，第二個序列中的數值代表體重。

輸出描述

排列結果，每個數值都是原始序列中的學生編號，編號從 1 開始

示例一

輸入

4
100 100 120 130
40 30 60 50

輸出

2134

示例二

輸入

3
90 110 90
45 60 45

輸出

132

解題思路

我們一共有三個列表，身高列表h，體重列表w，以及編號列表idx。

為了讓身高、體重和編號的信息能夠一一對應，我們使用zip()函數將這三個列表里面的內容綁定為一個包含n個三元元組的列表lst，即

lst = list(zip(h, w, idx))

在排序方面，題目要求我們按身高從小到大排序，身高相同再按體重從小到大排序，身高體重相同則按照編號從小到大排序，均為升序排序。所以直接調用列表的方法sort()或者內置函數sorted()即可完成。即

lst.sort()

最終再將排序后的lst中的編號信息取出來，再用字符串的join()方法將排序后的編號順序組合成一個字符串即可。即

print("".join([str(item[2]) for item in lst]))

代碼

# 題目：2023Q1A-身高提供排序
# 分值：100
# 作者：閉著眼睛學數理化
# 算法：直接調用排序API
# 代碼看不懂的地方，請直接在群上提問n = int(input())
h = list(map(int, input().split()))
w = list(map(int, input().split()))idx = [i for i in range(1, n+1)]    # 編號列表，1到n
lst = list(zip(h, w, idx))          # 身高、體重、編號整合為三元的元組，組成一個新的列表lstlst.sort()                 # 直接對lst排序，會先按照身高排序，再按照體重排序，再按照編號排序
print("".join(str(item[2]) for item in lst))   # 排序后取編號，組成字符串，即為答案

時空復雜度

時間復雜度：O(NlogN)。排序時間復雜度。

空間復雜度：O(N)。

進階

如果本題稍作修改，要求我們先按照身高升序排列，再按照體重降序排列，應該如何修改代碼呢？這個時候就要祭出神器lambda匿名函數了。語法如下：

lst.sort(key = lambda x: (x[0], -x[1]))  

key是sort()方法或sorted()內置函數的參數，表示排序的依據。lambda匿名函數中的x表示的就是lst中的元素，即一個個的三元元組。由于sort()默認的排序方式是升序，(x[0], -x[1])表示對列表先按照x[0]升序排列，在x[0]相同的情況下再按照-x[1]升序排列，即按照x[1]降序排列。通過這樣的方式，我們就實現了身高升序排列，再按照體重降序排列的目的。

對于原題目而言，如果我們也想顯式地寫出lambda匿名函數，則代碼為：

lst.sort(key = lambda x: (x[0], x[1]))  

如果還想再把編號按照升序排列也顯式地寫出，則代碼為

lst.sort(key = lambda x: (x[0], x[1], x[2]))  

lambda匿名函數的作用很多。除了sort()之外，取最值的兩個函數max()和min()中包含參數key，表示取最大值或最小值的依據，譬如：

max(lst, key = lambda x: x[0] * x[1]))

表示取身高和體重之積最大的那個人所對應的三元元組。

華為OD算法/大廠面試高頻題算法練習沖刺訓練

• 華為OD算法/大廠面試高頻題算法沖刺訓練目前開始常態化報名！目前已服務100+同學成功上岸！

• 課程講師為全網50w+粉絲編程博主@吳師兄學算法 以及小紅書頭部編程博主@閉著眼睛學數理化

• 每期人數維持在20人內，保證能夠最大限度地滿足到每一個同學的需求，達到和1v1同樣的學習效果！

• 60+天陪伴式學習，40+直播課時，300+動畫圖解視頻，300+LeetCode經典題，200+華為OD真題/大廠真題，還有簡歷修改、模擬面試、專屬HR對接將為你解鎖

• 可上全網獨家的歐弟OJ系統練習華子OD、大廠真題

• 可查看鏈接 OD算法沖刺訓練課程表 & OD真題匯總(持續更新)

• 綠色聊天軟件戳 od1336了解更多