ค้นหาตัวเลขที่ขาดหายไปสี่ตัวในอาร์เรย์ที่มีองค์ประกอบตั้งแต่ 1 ถึง N ใน Python

สมมติว่าเรามีอาร์เรย์ของตัวเลขที่แตกต่างกัน โดยที่แต่ละหมายเลขอยู่ในช่วง [1, N] ขนาดอาร์เรย์คือ (N-4) และไม่มีองค์ประกอบซ้ำกัน ดังนั้นเราจึงสามารถเข้าใจตัวเลขสี่ตัวตั้งแต่ 1 ถึง N ที่หายไปในอาร์เรย์ เราต้องหาตัวเลขที่หายไป 4 ตัวนี้ตามลำดับ

ดังนั้น หากอินพุตเป็น A =[2, 8, 4, 13, 6, 11, 9, 5, 10] ผลลัพธ์จะเป็น [1, 3, 7, 12]

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

• temp_arr :=อาร์เรย์ขนาด 4 ที่มี 0 ทั้งหมด

• สำหรับผมอยู่ในช่วง 0 ถึงขนาด A ทำ

  • อุณหภูมิ :=|A[i]|

  • ถ้า temp <=ขนาด A แล้ว

    • A[ชั่วคราว - 1] :=A[ชั่วคราว - 1] *(-1)

  • มิฉะนั้นเมื่อ temp> size ของ A แล้ว

    • ถ้า temp mod size ของ A ไม่ใช่ศูนย์ ดังนั้น

      • temp_arr[ขนาด mod ชั่วคราวของ A - 1] :=-1

    • มิฉะนั้น

      • temp_arr[(ขนาด mod ชั่วคราวของ A) +ขนาดของ A - 1] :=-1

• สำหรับผมอยู่ในช่วง 0 ถึงขนาด A ทำ

  • ถ้า A[i]> 0 แล้ว

    • แสดง i + 1

• สำหรับฉันอยู่ในช่วง 0 ถึงขนาดของ temp_arr ทำ

  • ถ้า temp_arr[i]>=0 แล้ว

    • ขนาดแสดงผล A + i + 1

ตัวอย่าง

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

def find_missing_nums(A) :
   temp_arr = [0]*4
   for i in range(0,len(A)) :
      temp = abs(A[i])
      if (temp <= len(A)) :
         A[temp - 1] = A[temp - 1] * (-1)
      elif (temp > len(A)) :
         if (temp % len(A)) :
            temp_arr[temp % len(A) - 1] = -1
         else :
            temp_arr[(temp % len(A)) +len(A) - 1] = -1
   for i in range(0, len(A) ) :
      if (A[i] > 0) :
         print((i + 1) , end=" ")
   for i in range(0, len(temp_arr)) :
      if (temp_arr[i] >= 0) :
         print((len(A) + i + 1) , end=" ")
A = [2, 8, 4, 13, 6, 11, 9, 5, 10]
find_missing_nums(A)

อินพุต

[2, 8, 4, 13, 6, 11, 9, 5, 10]

ผลลัพธ์

1 3 7 12