Python 程序在预期线性时间内从列表中选择第 n 个最大元素
pythonserver side programmingprogramming
当需要以线性时间复杂度从列表中选择第 n 个最大元素时，需要两种方法。一种方法是找到最大元素，另一种方法将列表分成两部分。此划分取决于用户给出的 ‘i’ 值。根据此值，拆分列表并确定最大元素。
下面是相同的演示 −
示例
def select_largest(my_list, beg, end, i):
if end - beg <= 1:
return my_list[beg]
pivot_val = start_partition(my_list, beg, end)
k = end - pivot_val
if i < k:
return select_largest(my_list, pivot_val + 1, end, i)
elif i > k:
return select_largest(my_list, beg, pivot_val, 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('输入数字列表.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('输入 i 的值.. '))
ith_largest = select_largest(my_list, 0, len(my_list), i)
print('结果为 {}.'.format(ith_largest))
输出
输入数字列表.. 34 67 12 0 999 输入 i 的值.. 1 结果为 999。
解释
定义了一个名为‘select_largest’的方法，该方法以列表、开头、结尾和一个‘i’值作为参数。
定义了另一个名为‘start_partition’的方法，该方法根据‘i’的值将列表分为两部分。
此方法在‘select_largest’方法中调用。
‘select_largest’也会在同一个函数中再次被调用 - 这就是递归的工作方式。
数字是从用户那里获取的。
它根据默认值进行拆分。
它被迭代。
‘i’ 的值是从用户那里获取的。
根据这个‘i’ 值，列表被分成两部分。
在其中一个列表上调用‘select_largest’ 方法。
输出显示在控制台上。
