Python 程序在预期的线性时间内从列表中选择第 n 个最小元素

  • Z时代
  • 2024-01-10
  • 分类：综合

当需要从线性时间复杂度的列表中选择第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”方法。

  • 输出显示在控制台上。

以上是 Python 程序在预期的线性时间内从列表中选择第 n 个最小元素 的全部内容， 来源链接： utcz.com/z/359296.html

回到顶部