โปรแกรมเพื่ออัปเดตองค์ประกอบในช่วงที่กำหนดใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และรายการการดำเนินการ ที่นี่แต่ละการดำเนินการมีสามฟิลด์ [L, R, X] ซึ่งบ่งชี้ว่าเราควรเพิ่ม X องค์ประกอบทั้งหมดจากดัชนี L ถึง R (รวม) เราต้องใช้การดำเนินการทั้งหมดและส่งคืนรายการสุดท้าย

ดังนั้น หากอินพุตเป็น nums =[8, 4, 2, -9, 4] operation =[ [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]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เหตุการณ์ :=รายการใหม่
• สำหรับแต่ละ (l, r, inc) ในการดำเนินการ ทำ
  • แทรก (l, inc) ที่ส่วนท้ายของกิจกรรม
  • แทรก (r + 1, -inc) ต่อท้ายกิจกรรม
• จัดเรียงรายการกิจกรรม
• inc :=0, ptr :=0
• สำหรับ i ในช่วง 0 ถึงขนาดของ nums ให้ทำ
  • ในขณะที่ 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]