資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 陣列排列，使其具有來自另一個數組的較小值
在本教程中，我們得到了兩個陣列 A 和 B。例如，我們需要輸出 A 的任何排列，以便最大化 A[I] > B[I] 的索引，例如
Input: A = [12, 22, 41, 13], B = [1, 20, 10, 12] Output: 12, 22, 41, 13 Input: A = [2, 5, 9, 7], B = [1, 12, 4, 54] Output: 2 7 5 9 Multiple answers can be present in that case we are simply going to print any one of the answers.
在這個問題中，我們需要最大化 A[i] > B[i] 的索引，所以我們將貪婪地解決這個問題。
查詢解決方案的方法
在這種方法中，我們將首先對這兩個陣列進行排序；我們貪婪地檢查陣列 B 的每個索引，使得 A[i] 比它更重要，然後將該元素放入向量中。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int A[] = { 2, 5, 9, 7 };
int B[] = { 1, 12, 4, 54 };
int n = sizeof(A) / sizeof(int); // size of our arrays
vector<pair<int, int> > A_pair, B_pair;
/***********************We are linking element to its position***********/
for (int i = 0; i < n; i++)
A_pair.push_back({A[i], i});
for (int i = 0; i < n; i++)
B_pair.push_back({B[i], i});
/***********************************************************************/
/*****Sorting our pair vectors********************/
sort(A_pair.begin(), A_pair.end());
sort(B_pair.begin(), B_pair.end());
int i = 0, j = 0, ans[n];
memset(ans, -1, sizeof(ans)); // initializing all the elements with value -1
vector<int> remaining; // this will store our elements which have lesser value than elemnt present in B.
while (i < n && j < n) {
// as our array is sorted then if we find any element in
//current index which has less value than B of current index then
// automatically it will have less value than other elements of B
// that's why we push such indices in remaining otherwise we push element in ans
if (A_pair[i].first > B_pair[j].first) {
ans[B_pair[j].second] = A_pair[i].first;
i++;
j++;
}
else {
remaining.push_back(i);
i++;
}
}
j = 0;
for (int i = 0; i < n; ++i){
// now if any index of answer is unchanged so that means
//we need to fill that position with the remaining elements
if (ans[i] == -1){
ans[i] = A_pair[remaining[j]].first;
j++;
}
}
for (int i = 0; i < n; i++) // printing our answer
cout << ans[i] << " ";
return 0;
}輸出
2 7 5 9
以上程式碼的解釋
在這種方法中，我們首先將所有元素與其索引關聯起來，以便在排序時仍然保留其舊索引。我們對這兩個元素對的向量進行排序，現在我們貪婪地搜尋我們的答案，當我們遍歷這兩個陣列時，如果我們得到 A_pair 的索引，其值大於 B_pair 的值，那麼我們將它儲存在我們的陣列中（以及在 B_pair 的位置），否則，因為我們已經對這兩個向量進行了排序，所以我們知道我們將無法使用這個 A_pair 的值，所以我們將該元素的索引推入我們的剩餘向量中，現在我們藉助剩餘向量填充陣列，然後我們列印答案。
結論
在本教程中，我們解決了一個問題，即查詢一個數組的排列，該陣列具有來自另一個數組的較小值。我們還學習了這個問題的 C++ 程式以及我們解決的完整方法。我們可以用其他語言（如 C、Java、Python 和其他語言）編寫相同的程式。我們希望您覺得本教程有所幫助。
更新於： 2021-11-25
111 次檢視
廣告