本教程中提供了两个数组 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等语言来编写同样的程序。我们希望本教程对您有所帮助。