Tối đa hóa các phần tử bằng cách sử dụng một mảng khác trong C ++

Tuyên bố vấn đề

Cho hai mảng có kích thước n, hãy tối đa hóa mảng đầu tiên bằng cách sử dụng các phần tử từ mảng thứ hai sao cho mảng mới được định dạng chứa n phần tử lớn nhất nhưng duy nhất của cả hai mảng có ưu tiên mảng thứ hai, tức là tất cả các phần tử của mảng thứ hai xuất hiện trước mảng thứ nhất mảng. Thứ tự xuất hiện của các phần tử phải được giữ nguyên ở đầu ra như ở đầu vào

Nếu arr1 [] ={12, 15, 10} và arr2 [] ={16, 17, 5} thì {16, 17, 15} là các phần tử lớn nhất từ ​​cả hai mảng bằng cách duy trì thứ tự.

Thuật toán

1. Create temporary array of size 2 * n
2. Store elements of arr1 and arr2 in temporary array and sort it in descending order
3. To keep the order of elements according to input arrays we will use hash table
4. Store first n largest unique elements of temporary array in hash table
5. Traverse the second array and store that elements of second array in temporary array that are present in hash table
6. Similarly, traverse the first array and store the elements that are present in hash table
7. In this way we get n unique and largest elements from both the arrays in temporary array

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void printArray(int *arr, int n){
   for (int i = 0; i < n; ++i) {
      cout << arr[i] << " ";
   }
   cout << endl;
}
bool compare(int a, int b){
   return a > b;
}
void getMaxElements(int *arr1, int *arr2, int n){
   int temp[2 * n];
   int k = 0;
   for (int i = 0; i < n; ++i) {
      temp[k] = arr1[i];
      ++k;
   }
   for (int i = 0; i < n; ++i) {
      temp[k] = arr2[i];
      ++k;
   }
   sort(temp, temp + 2 * n, compare);
   unordered_set<int> hash;
   int i = 0;
   while (hash.size() != n) {
      if (hash.find(temp[i]) == hash.end()) {
         hash.insert(temp[i]);
      }
      ++i;
   }
   k = 0;
   for (int i = 0; i < n; ++i) {
      if (hash.find(arr2[i]) != hash.end()) {
         temp[k++] = arr2[i];
         hash.erase(arr2[i]);
      }
   }
   for (int i = 0; i < n; ++i) {
      if (hash.find(arr1[i]) != hash.end()) {
         temp[k++] == arr1[i];
         hash.erase(arr1[i]);
      }
   }
   for (int i = 0; i < n; ++i) {
      arr1[i] = temp[i];
   }
}
int main(){
   int arr1[] = {12, 15, 10};
   int arr2[] = {16, 17, 5};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   cout << "First array:\n";
   printArray(arr1, n);
   cout << "Second array:\n";
   printArray(arr2, n);
   getMaxElements(arr1, arr2, n);
   cout << "Maximum array:\n";
   printArray(arr1, n);
   return 0;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

First array:
12 15 10
Second array:
16 17 5
Maximum array:
16 17 15