C++ Anordnung kleinerer Werte in einem anderen Array

In diesem Tutorial werden zwei Arrays A und B bereitgestellt. Zum Beispiel müssen wir jede Permutation von A ausgeben, sodass der Index bei A[ I ] > B[ I ] maximiert wird, wie zum Beispiel

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.

In diesem Problem müssen wir den Index bei A[ i ] > B maximieren [ i ] , also werden wir dieses Problem gierig lösen.

Methode zum Finden der Lösung

Bei dieser Methode sortieren wir nun zuerst beide Arrays; wir prüfen gierig jeden Index von Array B, sodass A[i] wichtiger ist als dieser, und fügen dann dieses Element zu einem Vektor hinzu.

Beispiel

#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;
}

Ausgabe

2 7 5 9

Erklärung des obigen Codes

Bei diesem Ansatz verknüpfen wir zunächst alle Elemente mit ihrem Index, sodass ihr alter Index beim Sortieren weiterhin erhalten bleibt. Wir sortieren die beiden Vektorpaare und suchen nun gierig nach der Antwort, während wir die beiden Arrays durchlaufen. Wenn wir den Index von A_pair erhalten, hat dieser einen höheren Wert als B_pair, also speichern wir ihn in unserem Array (und an der Position von B_pair). Andernfalls wissen wir, dass wir diesen Wert von A_pair nicht verwenden können, da wir beide Vektoren bereits sortiert haben. Deshalb verschieben wir diesen Elementindex in den verbleibenden Vektor und füllen nun das Array mit Hilfe des verbleibenden Vektors und drucken die Antwort.

Fazit

In diesem Tutorial haben wir ein Problem gelöst, um die Permutation eines Arrays mit kleineren Werten aus einem anderen Array zu finden. Wir haben auch ein C++-Programm für dieses Problem und unseren vollständigen Lösungsansatz kennengelernt. Wir können das gleiche Programm in anderen Sprachen wie C, Java, Python und anderen schreiben. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonC++ Anordnung kleinerer Werte in einem anderen Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!