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

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('输入数字列表.. ')
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’ 方法。

  • 在控制台上显示输出。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程