C++ 다른 배열에 더 작은 값 배열

이 튜토리얼에서는 두 개의 배열 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 ] , 그러니 우리는 이 문제를 과감하게 해결하겠습니다.

해결책을 찾는 방법

이 방법에서는 이제 두 배열을 먼저 정렬합니다. A[i]가 그보다 더 중요하도록 배열 B의 모든 인덱스를 탐욕스럽게 확인한 다음 해당 요소를 벡터에 추가합니다.

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

위 코드에 대한 설명

이 접근 방식에서는 먼저 모든 요소를 ​​해당 인덱스에 연결하여 정렬하는 동안 이전 인덱스가 계속 유지되도록 합니다. 우리는 두 개의 벡터 쌍을 정렬하고 이제 두 배열을 반복하면서 답을 탐욕스럽게 검색하고 A_pair의 인덱스를 얻으면 B_pair보다 우수한 값을 가지므로 배열에 저장합니다(그리고 B_pair의 위치). 그렇지 않으면 이미 두 벡터를 모두 정렬했기 때문에 A_pair의 이 값을 사용할 수 없다는 것을 알고 있으므로 해당 요소 인덱스를 나머지 벡터에 푸시하고 이제 나머지 벡터의 도움으로 배열을 채우고 인쇄합니다. 대답.

결론

이 튜토리얼에서는 다른 배열에서 더 작은 값을 가진 배열의 순열을 찾는 문제를 해결했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이를 해결하기 위한 완전한 접근 방식을 배웠습니다. C, Java, Python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되었기를 바랍니다.

위 내용은 C++ 다른 배열에 더 작은 값 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!