โปรแกรมหาปีประชากรสูงสุดโดยใช้ Python

สมมติว่าเรามีตารางที่มีสองคอลัมน์ (เกิด, ตาย) โดยที่แต่ละแถวแสดงถึงปีเกิดและการตายของบุคคลนั้น ประชากรของบางปี y คือจำนวนคนที่มีชีวิตอยู่ในช่วง y บุคคลที่ ith ถูกนับในประชากรปี y เมื่อ y อยู่ในช่วงรวม [birth_i, death_i - 1] (บุคคลนั้นไม่นับในปีที่เสียชีวิต). ดังนั้นเราต้องหาปีแรกสุดที่มีจำนวนประชากรสูงสุด

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 2 เพราะมีเพียงหนึ่งค่าที่ตรงกับเป้าหมาย นั่นคือ nums[4] ดังนั้น i =4 ตอนนี้ |4-2| =2.

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

• d :=แผนที่ ซึ่งหากไม่พบคีย์บางคีย์ ให้คืนค่า 0

• res :=รายการที่มีสองรายการ [2051, 0]

• สำหรับแต่ละปีเกิด YOB และปีที่เสียชีวิต YOD ในเมทริกซ์ ให้ทำ

  • สำหรับปีในช่วง YOB ถึง YOD ทำ

    • d[ปี] :=d[ปี] + 1

    • ถ้า d[ปี]>=res[1] แล้ว

      • ถ้า d[ปี]> res[1] แล้ว

        • res :=รายการที่มีสององค์ประกอบ [ปี, d[ปี]]

      • มิฉะนั้น

        • res :=รายการที่มีสององค์ประกอบ [(ขั้นต่ำของปีและ res[0]), res[1]]

• ผลตอบแทน[0]

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

from collections import defaultdict
def solve(matrix):
   d = defaultdict(int)
   res = [2051, 0]
   for YOB, YOD in matrix:
      for year in range(YOB, YOD):
         d[year] += 1
         if d[year] >= res[1]:
            if d[year] > res[1]:
               res = [year, d[year]]
            else:
               res = [min(year, res[0]), res[1]]
   return res[0]
matrix = [[1970,2010],[1960,2020],[1940,1970]]
print(solve(matrix))

อินพุต

[[1970,2010],[1960,2020],[1940,1970]]

ผลลัพธ์

1960