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
- while ptr <이벤트 및 이벤트의 크기[ptr, 0]은 i, do
- 반환 번호
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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]