Pythonで特定の範囲の要素を更新するプログラム

numsと呼ばれる数値のリストと演算のリストがあるとします。ここで、各操作には3つのフィールド[L、R、X]があります。これは、インデックスLからRまでのすべての要素をXずつインクリメントする必要があることを示しています。すべての操作を適用して、最終的なリストを返す必要があります。

したがって、入力がnums =[8、4、2、-9、4]のような場合操作=[[0、0、3]、[1、3、2]、[2、3、5]]、最初のリストは[8、4、2、-9、4]であったため、出力は[11、6、9、-2、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]になります。

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

• イベント：=新しいリスト
• 操作の（l、r、inc）ごとに、
  を実行します。
  • イベントの最後に（l、inc）を挿入
  • イベントの最後に（r + 1、-inc）を挿入します
• リストイベントを並べ替える
• inc：=0、ptr：=0
• 0からnumsのサイズの範囲のiの場合は、
  • ptr <イベントとイベントのサイズ[ptr、0]はiと同じですが、
    • inc：=inc + events [ptr、1]
    • ptr：=ptr + 1
  • nums [i]：=nums [i] + inc
• 数値を返す

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

例

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]