โปรแกรมค้นหาเซกเตอร์ที่เข้าชมมากที่สุดเป็นวงกลมโดยใช้ Python

สมมติว่าเรามีตัวเลข n และอาร์เรย์ที่เรียกว่า round เรามีเส้นทางวงกลมซึ่งประกอบด้วย n ส่วนต่างๆ ที่มีป้ายกำกับตั้งแต่ 1 ถึง n ตอนนี้พิจารณาการแข่งขันที่จะจัดขึ้นบนเส้นทางนี้ การแข่งขันประกอบด้วย m รอบที่แตกต่างกัน รอบที่ ith เริ่มต้นที่รอบเซกเตอร์[i - 1] และสิ้นสุดที่รอบเซกเตอร์[i] ตัวอย่างเช่น หากรอบที่ 1 เริ่มที่รอบเซกเตอร์[0] และสิ้นสุดที่รอบเซกเตอร์[1] ดังนั้นเราจึงต้องหาภาคที่เข้าชมมากที่สุดโดยเรียงลำดับจากน้อยไปมาก (หมายเลขแทร็กจะเรียงลำดับจากน้อยไปหามากในทิศทวนเข็มนาฬิกา)

ดังนั้น หากอินพุตเป็น n =4 รอบ =[1,3,1,2] ผลลัพธ์จะเป็น [1, 2]

เพราะการแข่งขันเริ่มจากเซกเตอร์ 1 ลำดับของเซกเตอร์ที่เข้าชมมีดังนี้ [1,2,3 (จบรอบแรก),4,1 (จบรอบที่สอง), 2 (จบรอบที่ 3)] ที่นี่ทั้งภาค 1 และ 2 มีการเยี่ยมชมสองครั้งและเป็นภาคส่วนที่มีผู้เข้าชมมากที่สุด และส่วนที่ 3 และ 4 เข้าชมเพียงครั้งเดียวเท่านั้น

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

• d :=แผนที่ใหม่

• สำหรับ j ในช่วง 1 ถึง n ทำ

  • d[j] :=0

• d[รอบ[0]] :=1

• สำหรับฉันในช่วง 1 ถึงขนาดของรอบ - 1 ทำ

  • ถ้า rounds[i]> rounds[i-1] แล้ว

    • สำหรับ j ในช่วง rounds[i-1]+1 ถึง rounds[i]+1 ทำ

      • d[j] :=d[j] + 1

  • มิฉะนั้น

    • สำหรับ j ในช่วง rounds[i-1]+1 ถึง n ทำ

      • d[j] :=d[j] + 1

    • สำหรับ j ในช่วง 1 ถึงปัดเศษ[i] ทำ

      • d[j] :=d[j] + 1

• curr :=d[rounds[0]]

• ออก :=[รอบ[0]]

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • ถ้าฉันไม่เหมือนกับ rounds[0] งั้น

    • ถ้า d[i]> curr แล้ว

      • สกุลเงิน :=d[i]

      • ออก :=[i]

    • มิฉะนั้นเมื่อ d[i] เหมือนกับ curr แล้ว

      • ต่อท้าย i โดยไม่ใช้

• กลับออกมาหลังจากจัดเรียง

ตัวอย่าง (Python)

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

def solve(n, rounds):
   d = {}
   for j in range(1,n+1):
      d[j] = 0
   d[rounds[0]] = 1
   for i in range(1, len(rounds)):
      if rounds[i] > rounds[i-1]:
         for j in range(rounds[i-1]+1, rounds[i]+1):
            d[j] += 1
      else:
         for j in range(rounds[i-1]+1,n+1):
            d[j] += 1
         for j in range(1,rounds[i]+1):
            d[j] += 1

   curr = d[rounds[0]]
   out = [rounds[0]]
   for i in range(1,n+1):
      if i != rounds[0]:
         if d[i] > curr:
            curr = d[i]
            out = [i]
         elif d[i] == curr:
            out = out + [i]
   return(sorted(out))

n = 4
rounds = [1,3,1,2]
print(solve(n, rounds))

อินพุต

4, [1,3,1,2]

ผลลัพธ์

[1, 2]