Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

Python에서 주어진 범위의 요소를 업데이트하는 프로그램

<시간/>

nums라는 숫자 목록과 작업 목록이 있다고 가정합니다. 여기서 각 연산에는 세 개의 필드 [L, R, X]가 있습니다. 이는 인덱스 L에서 R(포함)까지 모든 요소를 ​​X만큼 증가시켜야 함을 나타냅니다. 모든 작업을 적용하고 최종 목록을 반환해야 합니다.

따라서 입력이 nums =[8, 4, 2, -9, 4] operations =[ [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~숫자 크기 범위의 i에 대해
    • while ptr <이벤트 및 이벤트의 크기[ptr, 0]은 i, do
      • inc :=inc + 이벤트[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]