각 숫자가 [1, N] 범위에 있고 배열 크기가 (N-4)이고 단일 요소가 반복되지 않는 고유한 숫자의 배열이 있다고 가정합니다. 따라서 1에서 N까지 4개의 숫자가 배열에 누락되었음을 이해할 수 있습니다. 이 4개의 누락된 숫자를 정렬된 방식으로 찾아야 합니다.
따라서 입력이 A =[2, 8, 4, 13, 6, 11, 9, 5, 10]과 같으면 출력은 [1, 3, 7, 12]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
temp_arr :=모두 0인 크기 4의 배열
-
범위 0에서 A 크기까지의 i에 대해
-
온도 :=|A[i]|
-
temp <=크기 A 이면
-
A[온도 - 1] :=A[온도 - 1] *(-1)
-
-
그렇지 않으면 temp> A 크기일 때
-
A의 임시 모드 크기가 0이 아닌 경우
-
temp_arr[A - 1의 임시 모드 크기] :=-1
-
-
그렇지 않으면
-
temp_arr[(A의 임시 모드 크기) +A의 크기 - 1] :=-1
-
-
-
-
범위 0에서 A 크기까지의 i에 대해
-
A[i]> 0이면
-
디스플레이 i + 1
-
-
-
범위 0에서 temp_arr 크기까지의 i에 대해
-
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