ค้นหาดัชนีที่ดีทั้งหมดใน Array ที่กำหนดใน Python

สมมติว่าเรามีอาร์เรย์ A ของตัวเลข เราต้องหาดัชนีทั้งหมดของอาร์เรย์นี้ เพื่อที่ว่าหลังจากลบองค์ประกอบ ith ออกจากอาร์เรย์แล้ว อาร์เรย์จะเป็นอาร์เรย์ที่ดี เราต้องจำไว้ว่า -

• อาร์เรย์ที่ดีคืออาร์เรย์ที่มีองค์ประกอบที่เท่ากับผลรวมขององค์ประกอบอื่นๆ ทั้งหมด
• จะใช้การจัดทำดัชนีแบบ 1-based ที่นี่

ดังนั้นหากอินพุตเป็น [10, 4, 6, 2] เอาต์พุตจะเป็น [1,4] เช่นเดียวกับเมื่อเราลบ A[1] อาร์เรย์จะมีลักษณะดังนี้ [4, 6, 2] และมัน ดี เพราะ 6 =4+2 หากเราลบ A[4] อาร์เรย์จะมีลักษณะเป็น [10, 4, 6] และดีด้วย เช่น 10 =4+6

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

• n :=ขนาดของ A
• เพิ่ม :=0
• my_map :=แผนที่ใหม่
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • my_map[A[i]] :=my_map[A[i]] + 1
  • เพิ่ม :=เพิ่ม + A[i]
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • k :=เพิ่ม - A[i]
  • ถ้า k mod 2 เหมือนกับ 0 แล้ว
    • k :=k/2
    • ถ้า k ใน my_map แล้ว
      • ถ้า (A[i] เหมือนกับ k และ my_map[k]> 1) หรือ (A[i] ไม่เหมือนกับ k) ดังนั้น
        • แสดงผล i + 1

ตัวอย่าง

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

from collections import defaultdict
def find_indices(A):
   n = len(A)
   add = 0
   my_map = defaultdict(lambda:0)
   for i in range(n):
      my_map[A[i]] += 1
      add += A[i]
   for i in range(n):
      k = add - A[i]
      if k % 2 == 0:
         k = k >> 1
         if k in my_map:
            if ((A[i] == k and my_map[k] > 1) or (A[i] != k)):
               print((i + 1))
A = [10, 4, 6, 2]
find_indices(A)

อินพุต

[10, 4, 6, 2]

ผลลัพธ์

1
4