Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 다른 배열을 사용하여 요소 최대화

<시간/>

문제 설명

크기가 n인 두 개의 배열이 주어지면 두 번째 배열의 요소를 사용하여 첫 번째 배열을 최대화하여 새 arrayformed에 두 번째 배열 우선순위를 주는 두 배열의 가장 크지만 고유한 n개의 요소가 포함되도록 합니다. 즉, 두 번째 배열의 모든 요소가 첫 번째 배열보다 먼저 표시됩니다. 정렬. 요소의 출현 순서는 입력과 출력에서 ​​동일하게 유지되어야 합니다.

arr1[] ={12, 15, 10} 및 arr2[] ={16, 17, 5}인 경우 {16, 17, 15}는 순서를 유지하여 두 배열의 최대 요소입니다.

알고리즘

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

예시

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

출력

위 프로그램을 컴파일하고 실행할 때. 다음 출력을 생성합니다 -

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