数据结构
网络
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 次浏览
广告