Chương trình cập nhật các phần tử trong một phạm vi nhất định bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num và một danh sách các phép toán. Ở đây mỗi phép toán có ba trường [L, R, X], điều này chỉ ra rằng chúng ta nên tăng X tất cả các phần tử từ chỉ số L đến R (bao gồm). Chúng tôi phải áp dụng tất cả các thao tác và gửi lại danh sách cuối cùng.

Vì vậy, nếu đầu vào giống như nums =[8, 4, 2, -9, 4] các phép toán =[[0, 0, 3], [1, 3, 2], [2, 3, 5]], thì đầu ra sẽ là [11, 6, 9, -2, 4], như danh sách ban đầu là [8, 4, 2, -9, 4].

• Thực hiện thao tác đầu tiên [0, 0, 3] thì danh sách sẽ là [11, 4, 2, -9, 4].
• Thực hiện thao tác đầu tiên [1, 3, 2], danh sách sẽ là [11, 6, 4, -7, 4].
• Thực hiện thao tác đầu tiên [2, 3, 5], danh sách sẽ là [11, 6, 9, -2, 4].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sự kiện:=một danh sách mới
• đối với mỗi (l, r, inc) trong các phép toán, hãy thực hiện
  • chèn (l, inc) vào cuối sự kiện
  • chèn (r + 1, -inc) vào cuối sự kiện
• sắp xếp các sự kiện trong danh sách
• inc:=0, ptr:=0
• đối với tôi trong phạm vi từ 0 đến kích thước của nums, hãy thực hiện
  • while ptr
  • inc:=inc + sự kiện [ptr, 1]
  • ptr:=ptr + 1
• nums [i]:=nums [i] + inc

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

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

Đầu ra

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