C++で同じ順序を維持する2つの指定された配列からの最大配列

問題の説明

2つの同じサイズの配列A[]とB[]が与えられます。タスクは、同じサイズの3番目の配列を形成することです。結果の配列には、両方の配列から最大n個の要素が含まれている必要があります。最初にA[]の要素を選択し、次に元の配列に表示されるのと同じ順序でB[]の要素を選択する必要があります。共通の要素がある場合は、res []に1つの要素のみが存在し、A []

例

入力配列が-

arr1[] = {9, 17, 2, 25, 6}
arr2[] = {17, 4, 8, 10, 1} then final array is:
{9, 17, 25, 8, 10}

要素17が共通であり、arr1が優先されることに注意してください

アルゴリズム

• 両方のアレイのコピーを作成し、コピーを降順で並べ替えます
• ハッシュを使用して、両方の配列の一意のn個の最大要素を選択し、arr1 []
を優先します。
• 結果配列を空として初期化します
• arr1 []をトラバースし、ハッシュに存在するarr1[]の要素をコピーします。これは、要素の順序を同じに保つために行われます
• arr2[]に対して手順4を繰り返します。今回は、arr1 []
に存在しない要素のみを考慮します。

例

例を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
void printArray(vector<int> &arr, int n) {
   for (int i = 0; i < n; ++i) {
      cout << arr[i] << " ";
   }
   cout << endl;
}
void getMaxArray(int *arr1, int *arr2, int n) {
   vector<int> temp1(arr1, arr1 + n); vector<int> temp2(arr2, arr2 + n);
   sort(temp1.begin(), temp1.end(), greater<int>()); sort(temp2.begin(), temp2.end(), greater<int>());
   unordered_map<int, int> m;
   int i = 0, j = 0;
   while (m.size() < n) {
      if (temp1[i] >= temp2[j]) {
         m[temp1[i]]++;
         ++i;
      } else {
         m[temp2[j]]++;
         ++j;
      }
   }
   vector<int> result;
   for (int i = 0; i < n; ++i) {
      if (m.find(arr1[i]) != m.end()) {
         result.push_back(arr1[i]);
      }
   }
   for (int i = 0; i < n; ++i) {
      if (m.find(arr2[i]) != m.end() && m[arr2[i]] ==1) {
         result.push_back(arr2[i]);
      }
   }
   cout << "Final array:\n";
   printArray(result, n);
}
int main() {
   int arr1[] = {9, 17, 2, 25, 6};
   int arr2[] = {17, 4, 8, 10, 1};
   int n = sizeof(arr1) / sizeof(arr1[0]);
   getMaxArray(arr1, arr2, n);
   return 0;
}

出力

Final array:
9 17 25 8 10