C++에서 1에서 N까지의 요소를 포함하는 배열에서 4개의 누락된 숫자 찾기

컨셉

주어진 배열의 각 정수가 [1, N] 범위에 있는 고유 정수의 주어진 배열과 관련하여 배열의 크기는 (N-4)이고 단일 요소가 반복되지 않습니다. 따라서 1에서 N까지 4개의 숫자가 배열에서 누락되었습니다. 4개의 누락된 숫자를 정렬된 순서로 확인합니다.

입력

arr[] = {3, 6, 7, 4, 10}

출력

1 2 5 8 9

입력

arr[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 }

출력

1 3 7 12

방법

이제 간단한 O(N) 솔루션은 방문 요소를 표시하거나 표시하기 위해 크기가 N인 보조 배열을 구현하는 것입니다. 입력 배열을 방문하여 보조 배열의 요소를 표시하거나 표시합니다. 마침내 표시되거나 표시되지 않은 모든 색인을 인쇄하십시오.

이제 O(1) 보조 공간으로 해결하는 방법에 대한 질문이 제기됩니다.

처음에는 4개의 누락된 숫자를 보상하고 0으로 채우기 위해 길이가 4인 helper라는 배열을 초기화합니다. 그 후 우리는 i=0에서 주어진 배열의 i

• 요소의 절대값이 입력 배열의 길이보다 작으면 array[temp] 요소에 -1을 곱합니다(방문한 요소를 표시하거나 표시하기 위해).

• 요소의 절대값이 입력 배열의 길이보다 크면 helper[temp%array.length] 요소의 값을 -1로 지정합니다(방문한 요소를 표시하거나 표시하기 위해).

이제 입력 배열과 값이 여전히 0보다 큰 인덱스를 반복하고 입력 배열에서 해당 요소를 발견하지 못했습니다. 그 결과 요소가 0보다 큰 인덱스의 (index+1) 값을 출력합니다.

이제 도우미 배열과 값이 여전히 0보다 큰 인덱스를 반복하고 입력 배열에서 해당 요소를 만나지 못했습니다. 그 결과 요소가 0보다 큰 인덱스의 (index+array.length+1) 값을 인쇄합니다.

예

// CPP program to find missing 4 elements
// in an array of size N where elements are
// in range from 1 to N+4.
#include <bits/stdc++.h>
using namespace std;
// Used to find missing 4 numbers in O(N) time
// and O(1) auxiliary space.
void missing4(int arr1[], int n1){
   // Used to keep track of 4 possible numbers
   // greater than length of input array
   // In case of Java, helper is automatically
   // initialized as 0.
   int helper[4];
   // Visit the input array and mark
   // visited elements either by marking
   // them as negative in arr[] or in
   // helper[].
   for (int i = 0; i < n1; i++) {
      int temp1 = abs(arr1[i]);
      // It has been seen that if element is smaller than or
      // equal to length, mark its
      // presence in arr1[]
      if (temp1 <= n1)
         arr1[temp1 - 1] *= (-1);
      // Indicate or mark presence in helper[]
      else if (temp1 > n1) {
         if (temp1 % n1 != 0)
            helper[temp1 % n1 - 1] = -1;
         else
            helper[(temp1 % n1) + n1 - 1] = -1;
      }
   }
   // Used to print all those elements whose presence
   // is not marked.
   for (int i = 0; i < n1; i++)
      if (arr1[i] > 0)
         cout << (i + 1) << " ";
   for (int i = 0; i < 4; i++)
      if (helper[i] >= 0)
         cout << (n1 + i + 1) << " ";
      return;
}
// Driver code
int main(){
   int arr1[] = { 2, 8, 4, 13, 6, 11, 9, 5, 10 };
   int n1 = sizeof(arr1) / sizeof(arr1[0]);
   missing4(arr1, n1);
   return 0;
}

출력

1 3 7 12