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]

Arnab Chakraborty

更新于：2020年10月20日

265 次浏览

开启你的职业生涯

完成课程获得认证

开始学习