予想される線形時間のリストからn番目に小さい要素を選択するPythonプログラム

線形時間計算量でリストからn番目に小さい要素を選択する必要がある場合、2つの方法が必要です。最小の要素を見つける1つの方法と、リストを2つの部分に分割する別の方法。この区分は、ユーザーが指定した「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」値がパラメーターとして取得されます。

• 「i」の値に応じてリストを2つの部分に分割する、「start_partition」という名前の別のメソッドが定義されています。

• このメソッドは「select_smallest」メソッドで呼び出されます。

• 「select_smallest」も同じ関数内で再度呼び出されます。これが再帰の仕組みです。

• 数字はユーザーからの入力として取得されます。

• デフォルト値に基づいて分割されます。

• 繰り返されます。

• 「i」の値はユーザーから取得されます。

• この「i」の値に基づいて、リストは2つの部分に分けられます。

• 「select_smallest」メソッドは、リストの1つで呼び出されます。

• 出力はコンソールに表示されます。