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

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums of size n โดยที่ตัวเลขทั้งหมดในรายการจะอยู่ในช่วงเวลา [1, n] องค์ประกอบบางอย่างอาจปรากฏขึ้นสองครั้ง ในขณะที่บางรายการอาจมีเพียงครั้งเดียว เราต้องหาตัวเลขทั้งหมดจาก [1, n] ที่ไม่อยู่ในรายการ เราต้องส่งคืนตัวเลขที่เรียงลำดับจากน้อยไปมาก เราต้องพยายามหาวิธีแก้ปัญหาที่ใช้เวลาเชิงเส้นและพื้นที่คงที่

ดังนั้น หากอินพุตเป็น [4, 4, 2, 2, 6, 6] เอาต์พุตจะเป็น [1, 3, 5]

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

• arr :=อาร์เรย์ของขนาด nums + 1 และเติมด้วย 0
• สำหรับแต่ละ i ใน nums ทำ
  • arr[i] :=arr[i] + 1
• หายไป :=รายการใหม่
• สำหรับฉันในช่วง 0 ถึงขนาดของ arr ทำ
  • ถ้า arr[i] เหมือนกับ 0 และ i ไม่เหมือนกับ 0 แล้ว
    • ใส่ i ต่อท้ายส่วนที่ขาดหายไป
• ส่งคืนที่หายไป

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

ตัวอย่าง

class Solution:
   def solve(self, nums):
      arr = [0]*(len(nums)+1)
      for i in nums:
         arr[i] += 1
      missing = []
      for i in range(len(arr)):
         if arr[i] == 0 and i != 0:
            missing.append(i)
      return missing
ob = Solution()
print(ob.solve([4, 4, 2, 2, 6, 6]))

อินพุต

[4, 4, 2, 2, 6, 6]

ผลลัพธ์

[1, 3, 5]