Chương trình tìm tất cả các số còn thiếu từ 1 đến N bằng Python

Giả sử chúng ta có một danh sách các số được gọi là num có kích thước n trong đó tất cả các số trong danh sách đều có mặt trong khoảng [1, n] một số phần tử có thể xuất hiện hai lần trong khi các phần tử khác chỉ xuất hiện một lần. Chúng ta phải tìm tất cả các số từ [1, n] sao cho chúng không có trong danh sách. Chúng ta phải trả lại các số được sắp xếp theo thứ tự tăng dần. Chúng tôi phải cố gắng tìm ra một giải pháp cần thời gian tuyến tính và không gian ổn định.

Vì vậy, nếu đầu vào là [4, 4, 2, 2, 6, 6], thì đầu ra sẽ là [1, 3, 5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• arr:=một mảng có kích thước nums + 1 và điền bằng 0
• đối với mỗi tôi trong nums, thực hiện
  • arr [i]:=arr [i] + 1
• thiếu:=một danh sách mới
• đối với tôi trong phạm vi từ 0 đến kích thước của arr, thực hiện
  • nếu arr [i] giống 0 và i không giống 0, thì
    • chèn tôi vào cuối chỗ thiếu
• trả lại bị thiếu

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]))

Đầu vào

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

Đầu ra

[1, 3, 5]