ค้นหาองค์ประกอบที่หายไปจากอาร์เรย์ที่ซ้ำกันใน Python

สมมติว่าเรามีสองอาร์เรย์ที่ซ้ำกันยกเว้นหนึ่งองค์ประกอบ ดังนั้นองค์ประกอบหนึ่งจากอาร์เรย์ที่ระบุหายไป เราต้องหาองค์ประกอบที่ขาดหายไป

ดังนั้น หากอินพุตเป็น A =[2, 5, 6, 8, 10], B =[5, 6, 8, 10] เอาต์พุตจะเป็น 2 เนื่องจาก 2 หายไปจากอาร์เรย์ที่สอง

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

• กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา A, B, N

• ถ้า N เท่ากับ 1 แล้ว

  • กลับ A[0];

• ถ้า A[0] ไม่เหมือนกับ B[0] แล้ว

  • กลับ A[0]

• ต่ำ :=0, สูง :=N - 1

• ในขณะที่ต่ำ <สูง ทำ

  • กลาง :=(ต่ำ + สูง) / 2

  • ถ้า A[mid] เหมือนกับ B[mid] แล้ว

    • ต่ำ :=กลาง

  • มิฉะนั้น

    • สูง :=กลาง

  • ถ้าต่ำเท่ากับสูง - 1 แล้ว

    • ออกจากวง

• กลับ A[สูง]

• จากวิธีหลัก ให้ทำดังนี้ −

• M :=ขนาด A, N :=ขนาด B

• ถ้า N เหมือนกับ M-1 แล้ว

  • กลับแก้ (A, B, M)

• มิฉะนั้นเมื่อ M เหมือนกับ N-1 แล้ว

  • กลับแก้ (B, A, N)

• มิฉะนั้น

  • กลับ "ไม่พบ"

ตัวอย่าง

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

def solve(A, B, N):
   if N == 1:
      return A[0];
   if A[0] != B[0]:
      return A[0]
   low = 0
   high = N - 1
   while (low < high):
      mid = (low + high) / 2
      if A[mid] == B[mid]:
         low = mid
      else:
         high = mid
      if low == high - 1:
         break
   return A[high]
def get_missing_element(A, B):
   M = len(A)
   N = len(B)
   if N == M-1:
      return solve(A, B, M)
   elif M == N-1:
      return solve(B, A, N)
   else:
      return "Not found"

A = [2, 5, 6, 8, 10]
B = [5, 6, 8, 10]
print(get_missing_element(A, B))

อินพุต

[2, 5, 6, 8, 10], [5, 6, 8, 10]

ผลลัพธ์

2