Python程式：查詢兩個陣列元素乘積的第k大值

假設我們有兩個列表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大元素（索引從0開始）是16。

為了解決這個問題，我們將遵循以下步驟：

• 對列表p進行排序
• 對列表q進行排序
• k := k + 1
• 堆 := 列表表示的新堆
• 對於q中的每個元素，執行：
  • 如果元素 >= 0，則
    • 對於i從(p的大小 - 1)到-1遞減，執行：
      • cd := 元素 * p[i]
      • 如果堆不為空且堆的大小與k相同且cd <= 堆[0]，則
        • 退出迴圈
      • 將值cd插入堆中
      • 如果堆的長度 > k，則
        • 從堆中刪除最小項
  • 否則，
    • 對於i從0到p的大小，執行：
      • cd := 元素 * p[i]
      • 如果堆不為空且堆的大小與k相同且cd <= 堆[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

Arnab Chakraborty

更新於：2021年10月19日

191 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習