Pythonで線形時間のk番目に小さい要素を見つけるプログラム

numsという数値のリストがあり、別の値kもあるとすると、リスト内でk番目（0から始まる）の最小要素を見つける必要があります。この問題は平均してO（n）時間で解決する必要があります。

したがって、入力がnums =[6、4、9、3、1] k =2の場合、リストを並べ替えると[1、3、4、6、9]のようになり、出力は4になります。 、k番目に小さい要素は4です。

これを解決するには、次の手順に従います-

• maxHeap：=新しい空のヒープ
• 0からkの範囲のiについては、
  • nums[i]をmaxHeapに挿入
• k + 1の範囲のiからnums-1のサイズまで、do
  • nums [i]> maxHeap [0]の場合、
    • maxHeapからトップを削除
    • nums[i]をmaxHeapに挿入
• return maxHeap [0]

例

理解を深めるために、次の実装を見てみましょう-

from heapq import heappop, heappush
def solve(nums, k):
   maxHeap = []
   for i in range(k + 1):
      heappush(maxHeap, -nums[i])
   for i in range(k + 1, len(nums)):
      if nums[i] < -maxHeap[0]:
         heappop(maxHeap)
         heappush(maxHeap, -nums[i])
   return -maxHeap[0]

nums = [6, 4, 9, 3, 1]
k = 2
print(solve(nums, k))

入力

[6, 4, 9, 3, 1], 2

出力

4