Tìm bốn số còn thiếu trong một mảng chứa các phần tử từ 1 đến N bằng Python

Giả sử chúng ta có một mảng các số phân biệt trong đó mỗi số nằm trong phạm vi [1, N], kích thước mảng là (N-4) và không có phần tử nào được lặp lại. Vì vậy, chúng ta có thể hiểu bốn số, từ 1 đến N, bị thiếu trong mảng. Chúng ta phải tìm 4 số còn thiếu này theo cách sắp xếp.

Vì vậy, nếu đầu vào là A =[2, 8, 4, 13, 6, 11, 9, 5, 10], thì đầu ra sẽ là [1, 3, 7, 12]

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

• temp_arr:=một mảng có kích thước 4 với tất cả các số 0

• đối với tôi trong phạm vi từ 0 đến kích thước của A, hãy thực hiện

  • tạm thời:=| A [i] |

  • nếu temp <=size của A thì

    • A [temp - 1]:=A [temp - 1] * (- 1)

  • ngược lại khi temp> size của A thì

    • nếu kích thước mod tạm thời của A là khác 0, thì

      • temp_arr [kích thước mod tạm thời của A - 1]:=-1

    • nếu không,

      • temp_arr [(kích thước mod tạm thời của A) + kích thước của A - 1]:=-1

• đối với tôi trong phạm vi từ 0 đến kích thước của A, hãy thực hiện

  • nếu A [i]> 0, thì

    • hiển thị i + 1

• đối với tôi trong phạm vi từ 0 đến kích thước của temp_arr, hãy thực hiện

  • nếu temp_arr [i]> =0, thì

    • kích thước hiển thị của A + i + 1

Ví dụ

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

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)

Đầu vào

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

Đầu ra

1 3 7 12