C++ Arrangement of smaller values ​​in another array

Two arrays A and B are provided in this tutorial. For example, we need to output any arrangement of A such that the index of A[ I ] > B[ I ] is maximized, for example

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 this problem, we need to maximize A[ i ] > B[ i ], so we'll solve this problem greedily.

Method to find the solution

In this method, we now sort the two arrays first; we greedily check each index of array B such that A[i] is larger than It's more important then to put that element into a vector.

Example

#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

Explanation of the above code

In this approach we first link all the elements to their index so that Their old indexes are still retained when sorting. We sort the two vector pairs and now we greedily search for the answer while looping through the two arrays and if we get the index of A_pair it has a superior value than B_pair so we store it in our array (and at the position of B_pair) Otherwise, since we have already sorted both vectors, we know we won't be able to use this value of A_pair, so we push that element index into the remaining vector and now we fill the array with the help of the remaining vector and print the answer.

Conclusion

In this tutorial we solved a problem to find the permutation of an array with smaller values ​​from another array. We also learned a C program for this problem and our complete approach to solving it. We can write the same program in other languages ​​such as C, java, python and other languages. We hope you found this tutorial helpful.

The above is the detailed content of C++ Arrangement of smaller values ​​in another array. For more information, please follow other related articles on the PHP Chinese website!