Python程式：查詢k個和最大的子列表，並按升序返回這些和

假設我們有一個名為nums的數字列表，以及另一個值k，我們需要找到k個和最大的子列表，並按非遞減順序返回這些和。

因此，如果輸入類似於nums = [2, 4, 5, -100, 12, -30, 6, -2, 6] k = 3，則輸出將為[10, 11, 12]，因為我們有這3個和最大的子列表：[6, -2, 6]、[2, 4, 5]、[12]。

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

  • ps := 一個大小為nums大小+1的列表，並用0填充
  • 對於每個索引i和值v nums，執行以下操作：
    • ps[i + 1] := v + ps[i]
  • hp := 一個新的列表
  • 對於範圍從0到ps大小的i，執行以下操作：
    • 對於範圍從i+1到ps大小的j，執行以下操作：
      • 將-(ps[j] - ps[i])插入ps堆中
  • res := 彈出ps堆中的所有元素並反轉它們
  • 返回res

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

from heapq import heappop, heappush
class Solution:
   def solve(self, nums, k):
      ps = [0 for _ in range(len(nums) + 1)]
      for i, v in enumerate(nums):
         ps[i + 1] = v + ps[i]
      hp = []
      for i in range(len(ps)):
         for j in range(i + 1, len(ps)):
            heappush(hp, -(ps[j] - ps[i]))
            return list(reversed([-heappop(hp)
      for _ in range(k)]))
ob = Solution()
nums = [2, 4, 5, -100, 12, -30, 6, -2, 6] k = 3
print(ob.solve(nums, k))

輸入

[2, 4, 5, -100, 12, -30, 6, -2, 6],3

輸出

[10, 11, 12]

更新於: 2020年11月19日

124次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

立即開始
廣告