C++ より小さい値を別の配列に配置する

このチュートリアルでは、2 つの配列 A と B が提供されます。たとえば、A[ I ] > B[ I ] のインデックスが最大化されるような A の配置を出力する必要があります。たとえば

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 ] なので、この問題を貪欲に解きます。

解決策を見つける方法

この方法では、まず 2 つの配列を並べ替えます。配列 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

上記のコードの説明

このアプローチでは、最初にすべての要素をインデックスにリンクします。ソート時にも保持されます。 2 つのベクトルのペアをソートし、2 つの配列をループしながら答えを貪欲に検索します。A_pair のインデックスを取得すると、そのインデックスは B_pair よりも優れた値を持つため、配列 (および B_pair の位置) に保存します。それ以外の場合は、両方のベクトルを既にソートしているため、A_pair のこの値を使用できないことがわかっているため、その要素インデックスを残りのベクトルにプッシュし、残りのベクトルを利用して配列を埋めて出力します。答え。

結論

このチュートリアルでは、別の配列からのより小さい値を持つ配列の順列を見つける問題を解決しました。また、この問題に対する C プログラムと、それを解決するための完全なアプローチも学びました。同じプログラムを C、Java、Python などの他の言語で書くことができます。このチュートリアルがお役に立てば幸いです。

以上がC++ より小さい値を別の配列に配置するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。