資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式在預期線性時間內從列表中選擇第n個最小元素
當需要線上性時間複雜度內從列表中選擇第n個最小元素時，需要兩種方法。一種方法是找到最小元素，另一種方法是將列表分成兩部分。這種劃分取決於使用者提供的“i”值。根據此值，列表被分割，並確定最小元素。
以下是相同內容的演示 -
示例
def select_smallest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = pivot_val - beg + 1
if i < k:
return select_smallest(my_list, beg, pivot_val, i)
elif i > k:
return select_smallest(my_list, pivot_val + 1, end, i - k)
return my_list[pivot_val]
def start_partition(my_list, beg, end):
pivot_val = my_list[beg]
i = beg + 1
j = end - 1
while True:
while (i <= j and my_list[i] <= pivot_val):
i = i + 1
while (i <= j and my_list[j] >= pivot_val):
j = j - 1
if i <= j:
my_list[i], my_list[j] = my_list[j], my_list[i]
else:
my_list[beg], my_list[j] = my_list[j], my_list[beg]
return j
my_list = input('Enter the list of numbers.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('Enter the value for i.. '))
ith_smallest = select_smallest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_smallest))輸出
Enter the list of numbers.. 43 12 67 89 99 0 Enter the value for i.. 3 The result is 43.
解釋
定義了一個名為“select_smallest”的方法，它將列表、開頭、結尾和“i”值作為引數。
定義了另一個名為“start_partition”的方法，它根據“i”的值將列表分成兩部分。
此方法在“select_smallest”方法中被呼叫。
“select_smallest”也在同一函式內部再次被呼叫 - 這就是遞迴的工作原理。
從使用者處獲取數字作為輸入。
它基於預設值進行分割。
它被迭代。
從使用者處獲取“i”的值。
基於此“i”值，列表被分成兩部分。
“select_smallest”方法被呼叫到其中一個列表上。
輸出顯示在控制檯上。
更新於: 2021年4月14日
388 次檢視
廣告