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

Khái niệm

Đối với một mảng các số nguyên duy nhất đã cho trong đó mỗi số nguyên của mảng đã cho nằm trong phạm vi [1, N], kích thước của mảng là (N-4) và không có phần tử nào được lặp lại. Vì vậy, bốn số, từ 1 đếnN, bị thiếu trong mảng. Xác định 4 số còn thiếu theo thứ tự đã sắp xếp.

Đầu vào

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

Đầu ra

1 2 5 8 9

Đầu vào

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

Đầu ra

1 3 7 12

Phương pháp

Bây giờ, một giải pháp O (N) đơn giản là triển khai một mảng phụ trợ có kích thước N để biểu thị hoặc các thành phần được đánh dấu. Truy cập vào mảng đầu vào và chỉ ra hoặc đánh dấu các phần tử trong mảng phụ trợ. Ở lần in cuối cùng, tất cả các chỉ mục không được chỉ định hoặc đánh dấu.

Bây giờ câu hỏi được đặt ra là làm thế nào để giải quyết với O (1) không gian phụ?

Đầu tiên, chúng tôi khởi tạo một mảng có tên là helper có độ dài 4 để bù cho 4 số bị thiếu và điền chúng bằng 0. Sau đó, chúng ta lặp lại từ i =0 đến i

• Người ta thấy rằng nếu giá trị tuyệt đối của phần tử nhỏ hơn độ dài của mảng đầu vào thì chúng tôi sẽ nhân phần tử [temp] của mảng với -1 (để chỉ ra hoặc đánh dấu phần tử được truy cập).

• Người ta thấy rằng nếu giá trị tuyệt đối của phần tử lớn hơn độ dài của mảng đầu vào thì chúng ta sẽ đặt giá trị của phần tử helper [temp% array.length] bằng -1 (để chỉ ra hoặc đánh dấu phần tử được truy cập).

Bây giờ chúng ta lặp lại mảng đầu vào và những chỉ mục có giá trị vẫn lớn hơn 0 thì các thành phần đó không được gặp trong mảng đầu vào. Do đó, chúng tôi in ra giá trị (chỉ mục + 1) của chỉ mục có phần tử lớn hơn 0.

Bây giờ chúng ta sẽ lặp qua mảng trợ giúp và những chỉ mục có giá trị vẫn lớn hơn 0 thì các thành phần đó không được gặp trong mảng đầu vào. Do đó, chúng tôi in ra giá trị (index + array.length + 1) của chỉ mục có phần tử lớn hơn 0.

Ví dụ

// 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;
}

Đầu ra

1 3 7 12