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&#39;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等語言來寫同樣的程式。我們希望本教學對您有所幫助。

以上是C++另一個數組中較小值的排列的詳細內容。更多資訊請關注PHP中文網其他相關文章！