C++ Disposition des valeurs plus petites dans un autre tableau

Deux tableaux A et B sont fournis dans ce tutoriel. Par exemple, nous devons générer toute permutation de A telle que l'index à A[ I ] > B[ I ] soit maximisé, comme

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.

Dans ce problème, nous devons maximiser l'index à A[ i ] > B [ i ] , nous allons donc résoudre ce problème avec avidité.

Méthode pour trouver la solution

Dans cette méthode, nous trions maintenant d'abord les deux tableaux ; nous vérifions avidement chaque index du tableau B de telle sorte que A[i] soit plus important que lui, puis ajoutons cet élément dans un vecteur.

Exemple

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

Output

2 7 5 9

Explication du code ci-dessus

Dans cette approche, nous lions d'abord tous les éléments à leur index afin que leur ancien index soit toujours conservé lors du tri. Nous trions les deux paires de vecteurs et maintenant nous recherchons avidement la réponse en parcourant les deux tableaux et si nous obtenons l'index de A_pair il a une valeur supérieure à celle de B_pair donc nous le stockons dans notre tableau (et à la position de B_pair) Sinon , puisque nous avons trié les deux vecteurs, nous savons que nous ne pourrons pas utiliser cette valeur de A_pair, nous poussons donc cet index d'élément dans le vecteur restant, et maintenant nous remplissons le tableau à l'aide du vecteur restant et imprimons le répondre.

Conclusion

Dans ce tutoriel, nous avons résolu un problème pour trouver la permutation d'un tableau avec des valeurs plus petites provenant d'un autre tableau. Nous avons également appris un programme C++ pour ce problème et notre approche complète pour le résoudre. Nous pouvons écrire le même programme dans d'autres langages tels que C, Java, Python et d'autres langages. Nous espérons que vous avez trouvé ce tutoriel utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!