Giả sử chúng ta muốn phát triển một cấu trúc dữ liệu có thể xây dựng với một danh sách các số nguyên và có một hàm để tìm tổng các phần tử từ chỉ mục i đến chỉ mục j-1 bất cứ khi nào chúng ta yêu cầu một cách hiệu quả. Có hai chức năng.
- Hàm tạo xây dựng một phiên bản mới với mảng số nguyên.
- get_sum (i, j) trả về tổng các số nguyên của các phần tử mảng từ chỉ số bắt đầu i và chỉ số kết thúc j-1.
Vì vậy, nếu đầu vào giống như mảng =[5,2,3,6,4,7,8,9,3,2] thì hãy xây dựng một đối tượng obj và gọi các hàm obj.get_sum (1,5) và obj. get_sum (4,8), thì kết quả đầu ra sẽ là 15 và 28 tương ứng. Vì các phần tử phạm vi đầu tiên là [2,3,6,4] nên tổng là 15 và các phần tử phạm vi thứ hai là [4,7,8,9] ở đây tổng là 28.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định hàm tạo. Điều này sẽ lấy mảng
- sums:=đây là một danh sách, ban đầu hãy chèn 0
- đối với mỗi x trong mảng, thực hiện
- chèn (x + (mục cuối cùng của tổng)) vào cuối tổng
- Xác định một hàm get_sum (). Điều này sẽ mất tôi, j
- trả về tổng [j] - tổng [i]
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class RangeSum: def __init__(self, array): self.sums = [0] for x in array: self.sums.append(x + self.sums[-1]) def get_sum(self, i, j): return self.sums[j] - self.sums[i] array = [5,2,3,6,4,7,8,9,3,2] obj = RangeSum(array) print(obj.get_sum(1,5)) print(obj.get_sum(4,8))
Đầu vào
[5,2,3,6,4,7,8,9,3,2] obj.get_sum(1,5) obj.get_sum(4,8)
Đầu ra
15 28