資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學使用另一個數組使元素最大化（C++）
問題陳述
給定兩個大小為 n 的陣列，利用第二個陣列中的元素來最大化第一個陣列，使形成的新陣列包含兩個陣列的 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
更新日期： 2019-12-24
862 次瀏覽
廣告