ค้นหาองค์ประกอบที่แบ่งอาร์เรย์ออกเป็นสองอาร์เรย์ย่อยด้วยผลิตภัณฑ์ที่เท่ากันในPython

สมมติว่าเรามีอาร์เรย์ขนาด N; เราต้องหาองค์ประกอบที่แบ่งอาร์เรย์ออกเป็นสองอาร์เรย์ย่อยที่แตกต่างกันโดยมีผลคูณเท่ากัน คืนค่า -1 หากไม่มีพาร์ติชั่นดังกล่าว

ดังนั้น หากอินพุตเป็น [2,5,3,2,5] เอาต์พุตจะเป็น 3 ดังนั้นอาร์เรย์ย่อยจะเป็น:{2, 5} และ {2, 5}

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

• n :=ขนาดของอาร์เรย์
• multiply_pref :=รายการใหม่
• แทรกอาร์เรย์[0] ที่ส่วนท้ายของ multiply_pref
• สำหรับฉันในช่วง 1 ถึง n ทำ
  • แทรก multiply_pref[i-1]*array[i] ที่ส่วนท้ายของ multiply_pref
• multiply_suff :=รายการขนาด n และเติมไม่มี
• multiply_suff[n-1] :=array[n-1]
• สำหรับ i ในช่วง n-2 ถึง -1, ลดลง 1, ทำ
  • multiply_suff[i] :=multiply_suff[i+1]*array[i]
• สำหรับฉันอยู่ในช่วง 1 ถึง n-1 ทำ
  • ถ้า multiply_pref[i] เหมือนกับ multiply_suff[i] แล้ว
    • กลับอาร์เรย์[i]
• คืน -1

โค้ดตัวอย่าง

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

def search_elem(array):
   n = len(array)
   multiply_pref = []
   multiply_pref.append(array[0])
   for i in range(1, n):
      multiply_pref.append(multiply_pref[i-1]*array[i])
   multiply_suff = [None for i in range(0, n)]
   multiply_suff[n-1] = array[n-1]
   for i in range(n-2, -1, -1):
      multiply_suff[i] = multiply_suff[i+1]*array[i]
   for i in range(1, n-1):
      if multiply_pref[i] == multiply_suff[i]:
         return array[i]
   return -1
array = [2,5,3,2,5]
print(search_elem(array))

อินพุต

[2,5,3,2,5]

ผลลัพธ์

3