第七周作業（北大選課同學選做）
題目
1.快速排序主元（10分）
題目內容：著名的快速排序演算法里有一個經典的劃分程序：我們通常采用某種方法取一個元素作為主元（中值），通過交換，把比主元小的元素放到它的左邊，比主元大的元素放到它的右邊， 給定劃分后的N個互不相同的正整數的排列，請問有多少個元素可能是劃分前選取的主元？
例如給定的排列是[1, 3, 2, 4, 5]，則：1 的左邊沒有元素，右邊的元素都比它大，所以它可能是主元；盡管 3 的左邊元素都比它小，但其右邊的 2 比它小，所以它不能是主元；盡管 2 的右邊元素都比它大，但其左邊的 3 比它大，所以它不能是主元；類似原因，4 和 5 都可能是主元，因此，有 3 個元素可能是主元，
輸入格式:
一行數個整數的排列，由空格分隔
輸出格式：
在第 1 行中輸出有可能是主元的元素個數；在第 2 行中按遞增順序輸出這些元素，其間以 1 個空格分隔，行首尾不得有多余空格，
輸入樣例：1 3 2 4 5
輸出樣例：
3
1 4 5
時間限制：500ms 記憶體限制：32000kb
思路
本頭腦簡單想出的頭腦簡單思路，極有可能時間或記憶體超出限制（記錄完這篇就去看看大佬的思路），判斷一個數是否主元，如果這個數左邊的數都比他小，并且右邊的數都比他大，他就是主元，
即：
- 條件1：左邊這部分串列的最大值，小于等于這個數，（如果左邊沒有數值則默認其滿足條件1）
- 條件2：右邊這部分串列的最小值，大于等于這個數，（如果右邊沒有數值則默認滿足條件2）
使用if的or陳述句判斷條件時，把判斷串列是否為空寫在or前面，如果串列空，就不再判斷or后面的條件，因為max()執行的物件是空串列，就會報錯，
代碼
def judge_mid(blist):
#將輸入的字串轉換成數字串列
alist = []
for i in blist.split():
alist.append(int(i))
Mid_list = []
#比較左右數值判斷主元，Mid_list串列記錄主元
for position in range(len(alist)):
if alist[:position]==[] or max(alist[:position])<=alist[position]:
if alist[position+1:]==[] or min(alist[position+1:])>=alist[position]:
Mid_list.append(alist[position])
print(len(Mid_list))
#升序排序、將串列轉換數字字串輸出
Mid_list.sort()
for i in Mid_list:
print(i, end=' ')
blist = input()
judge_mid(blist)
歡迎指正
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/162241.html
標籤：其他
上一篇：【Python】從0到1：30行代碼制作表白視窗！(可直接copy + 運行哦~)
下一篇：Python 使用 asyncio 時出現 RuntimeError: This event loop is already running 的解決方法