数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：在预期线性时间内从列表中选择第n大元素
当需要在线性时间复杂度内从列表中选择第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('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_largest = select_largest(my_list, 0, len(my_list), i)
print('The result is {}.'.format(ith_largest))输出
Enter the list of numbers.. 34 67 12 0 999 Enter the value for i.. 1 The result is 999.
解释
定义了一个名为“select_largest”的方法，该方法将列表、起始位置、结束位置和'i'值作为参数。
定义了另一个名为“start_partition”的方法，该方法根据'i'值将列表分成两部分。
此方法在“select_largest”方法中被调用。
“select_largest”也在同一个函数内部再次被调用——这就是递归的工作方式。
数字从用户处作为输入获取。
它基于默认值进行分割。
它被迭代。
从用户处获取'i'的值。
基于此'i'值，列表被分成两部分。
“select_largest”方法被调用在一个列表上。
输出显示在控制台上。
更新于：2021年4月15日
370 次浏览
广告