สมมติว่าเราต้องการพัฒนาโครงสร้างข้อมูลที่สามารถสร้างรายการจำนวนเต็มได้ และมีฟังก์ชันในการค้นหาผลรวมขององค์ประกอบตั้งแต่ดัชนี i ถึงดัชนี j-1 เมื่อใดก็ตามที่เราต้องการอย่างมีประสิทธิภาพ มีสองหน้าที่
- ตัวสร้างที่สร้างอินสแตนซ์ใหม่ด้วยอาร์เรย์จำนวนเต็ม
- get_sum(i, j) คืนค่าผลรวมของจำนวนเต็มขององค์ประกอบอาร์เรย์จากดัชนีเริ่มต้น i และดัชนีสิ้นสุด j-1
ดังนั้น ถ้าอินพุตเป็นเหมือนอาร์เรย์ =[5,2,3,6,4,7,8,9,3,2] ให้สร้างวัตถุ obj และเรียกใช้ฟังก์ชัน obj.get_sum(1,5) และ obj get_sum(4,8) ดังนั้นผลลัพธ์จะเป็น 15 และ 28 ตามลำดับ เนื่องจากองค์ประกอบช่วงแรกคือ [2,3,6,4] ผลรวมคือ 15 และองค์ประกอบช่วงที่สองคือ [4,7,8,9] ผลรวมคือ 28
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดคอนสตรัคเตอร์ นี่จะเป็นอาร์เรย์
- sums :=นี่คือรายการ เริ่มแรกให้ใส่ 0
- สำหรับแต่ละ x ในอาร์เรย์ ทำ
- แทรก (x + (รายการสุดท้ายของผลรวม)) ที่ส่วนท้ายของผลรวม
- กำหนดฟังก์ชัน get_sum() นี่จะใช้เวลา i, j
- ผลตอบแทนรวม[j] - ผลรวม[i]
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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))
อินพุต
[5,2,3,6,4,7,8,9,3,2] obj.get_sum(1,5) obj.get_sum(4,8)
ผลลัพธ์
15 28
