Python 更新指定範圍內的元素程式

假設我們有一個名為 nums 的數字列表和一個操作列表。每個操作都有三個欄位 [L, R, X]，這表示我們應該將索引 L 到 R（包含）之間的所有元素增加 X。我們必須應用所有操作並返回最終列表。

因此，如果輸入類似於 nums = [8, 4, 2, -9, 4] operations = [ [0, 0, 3], [1, 3, 2], [2, 3, 5] ]，則輸出將為 [11, 6, 9, -2, 4]，因為初始列表為 [8, 4, 2, -9, 4]。

  • 執行第一個操作 [0, 0, 3]，列表將變為 [11, 4, 2, -9, 4]。
  • 執行第二個操作 [1, 3, 2]，列表將變為 [11, 6, 4, -7, 4]。
  • 執行第三個操作 [2, 3, 5]，列表將變為 [11, 6, 9, -2, 4]。

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

  • events := 新建一個列表
  • 對於 operations 中的每個 (l, r, inc)，執行：
    • 在 events 的末尾插入 (l, inc)
    • 在 events 的末尾插入 (r + 1, -inc)
  • 對 events 列表進行排序
  • inc := 0, ptr := 0
  • 對於範圍 0 到 nums 的大小，執行：
    • 當 ptr < events 的大小且 events[ptr, 0] 等於 i 時，執行：
      • inc := inc + events[ptr, 1]
      • ptr := ptr + 1
    • nums[i] := nums[i] + inc
  • 返回 nums

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

示例

 線上演示

class Solution:
   def solve(self, nums, operations):
      events = []
      for l, r, inc in operations:
         events.append((l, inc))
         events.append((r + 1, -inc))
      events.sort()
      inc = 0
      ptr = 0
      for i in range(len(nums)):
         while ptr < len(events) and events[ptr][0] == i:
            inc += events[ptr][1]
            ptr += 1
         nums[i] += inc
      return nums
ob = Solution()
nums = [8, 4, 2, -9, 4]
operations = [ [0, 0, 3], [1, 3, 2], [2, 3, 5] ]
print(ob.solve(nums, operations))

輸入

[1,2,3,4,5,6,7,8,9,10], 3

輸出

[11, 6, 9, -2, 4]

更新於：2020年10月20日

265 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告