Pythonで2つの配列の要素のk番目に大きい積を見つけるプログラム

いくつかの整数を含む2つのリストpとqが与えられたと仮定します。これらのリストのすべての値を乗算し、乗算結果からk番目に大きい値を見つける必要があります。

したがって、入力がp =[2、5]、q =[6、8]、k =2の場合、出力は16になります。

乗算の結果は次のとおりです。2*6=12、2 * 8 =16、5 * 6 =30、5 * 8 =40。2番目に大きい要素はis（インデックスは0から始まります）は16です。

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

• リストを並べ替えるp
• リストを並べ替えるq
• k：=k + 1
• ヒープ：=リスト表現の新しいヒープ
• qの各要素について、
  • elem> =0の場合、
    • iの範囲（p-1のサイズ）から-1の場合、1ずつ減少します。
      • cd：=elem * p [i]
      • ヒープが空でなく、ヒープのサイズがkおよびcdと同じである場合<=heap [0]、
        • ループから抜け出す
      • 値cdをヒープに挿入します
      • （ヒープ）の長さが> kの場合、
        • ヒープから最小のアイテムを削除する
  • それ以外の場合、
    • 0からpのサイズの範囲のiについては、
      • cd：=elem * p [i]
      • ヒープが空でなく、ヒープのサイズがkおよびcdと同じである場合<=heap [0]、
        • ループから抜け出す
      • CDをヒープに挿入
      • （ヒープ）> kの長さがゼロ以外の場合、
        • ループから最小のアイテムを削除します
• ヒープを返す[0]

例

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

from heapq import heappush, heappop
def solve(p, q, k):
p = sorted(p)
q = sorted(q)
k += 1
heap = []
for elem in q:
if elem >= 0:
for i in range((len(p) - 1), -1, -1):
cd = elem * p[i]
if heap and len(heap) == k and cd <= heap[0]:
break
heappush(heap, cd)
if len(heap) > k:
heappop(heap)
else:
for i in range(len(p)):
cd = elem * p[i]
if heap and len(heap) == k and cd <= heap[0]:
break
heappush(heap, cd)
if len(heap) > k:
heappop(heap)
return heap[0]
print(solve([2, 5], [6, 8], 2))

入力

[2, 5], [6, 8], 2

出力

16