ตรวจสอบว่าอย่างน้อย half array ลดลงเหลือศูนย์โดยดำเนินการบางอย่างใน Python

สมมติ เราได้รับรายการขนาด n ที่มีจำนวนเต็มบวกและจำนวนเต็มบวก m อีกจำนวนหนึ่ง สมมติว่าขณะนี้เราอยู่ในลูปและการวนซ้ำแต่ละครั้ง เราลดค่าขององค์ประกอบบางรายการในอาร์เรย์ลง 1 และเพิ่มมูลค่าขององค์ประกอบที่เหลือโดย m เราต้องค้นหาว่าองค์ประกอบของรายการครึ่งหนึ่งหรือมากกว่านั้นกลายเป็นศูนย์หลังจากการทำซ้ำบางส่วนหรือไม่ เราจะคืนค่า True หากเป็นไปได้ และคืนค่าเป็น False หากไม่ใช่

ดังนั้น หากอินพุตเป็นเหมือน input_list =[10, 18, 35, 5, 12], m =4 ผลลัพธ์จะเป็น True

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

• frequency_list :=รายการใหม่ของขนาด m+1 เริ่มต้นด้วย 0
• ผม :=0
• ในขณะที่ฉัน <ขนาดของ input_list ทำ

  • frequency_list[input_list[i] mod(m + 1) ] :=

    frequency_list[input_list[i] mod (m + 1) ] + 1

  • ผม :=ผม + 1
• ผม :=0
• ในขณะที่ฉัน <=m ทำ
  • ถ้า frequency_list[i]>=(ขนาดของ input_list / 2) แล้ว
    • ออกมาจากวงจร
  • ผม :=ผม + 1
• ถ้าฉัน <=m แล้ว
  • คืนค่า True
• มิฉะนั้น
  • คืนค่าเท็จ

ตัวอย่าง

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

def solve(input_list, m):
   frequency_list = [0] * (m + 1)
   i = 0
   while(i < len(input_list)):
      frequency_list[(input_list[i] % (m + 1))] += 1
      i += 1
   i = 0
   while(i <= m):
      if(frequency_list[i] >= (len(input_list)/ 2)):
         break
      i += 1
   if (i <= m):
      return True
   else:
      return False
input_list = [10, 18, 35, 5, 12]
print(solve(input_list, 4))

อินพุต

[10, 18, 35, 5, 12], 4

ผลลัพธ์

True