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('输入数字列表.. ')
my_list = my_list.split()
my_list = [int(x) for x in my_list]
i = int(input('输入i的值.. '))

ith_smallest = select_smallest(my_list, 0, len(my_list), i)
print('结果是{}。'.format(ith_smallest))

输出

输入数字列表.. 43 12 67 89 99 0
输入i的值.. 3
结果是43。

说明

• 定义了一个名为’select_smallest’的方法，该方法将列表，开始，结束和’i’值作为参数。

• 定义了另一个名为“start_partition”的方法，该方法根据“i”的值将列表分成两部分。

• 此方法在“select_smallest”方法中调用。

• ‘select_smallest’方法再次在同一函数内调用-这就是递归的工作原理。

• 从用户输入数字。

• 根据默认值拆分。

• 迭代它。

• 从用户处获取’i’的值。

• 根据此“i”值，将列表分为两部分。

• 基于其中一个列表调用“select_smallest”方法。

• 在控制台上显示结果。