C++で配列をソート済みにできる別の配列の最大要素の求め方

問題概要

数値の配列 Arr1[] と、同じ長さまたは異なる長さの別の配列 Arr2[] が与えられます。Arr1[] の要素は昇順にソートされていますが、ただ一つの要素だけが誤った位置に配置されています。この課題では、Arr2[] から適切な要素を選び、Arr1[] の誤った位置にある要素を置き換えることで、配列全体をソート済みの状態にします。置き換えに使える候補が複数ある場合は、その中で最大の要素を選択しなければなりません。

入力例 1

Arr1[]= { 1,3,5,7,2,11 }, Arr2[]= { 4,8,7,10,9 }

出力例 1

Arr1 をソートできる最大の要素: 10

解説: Arr2[] のうち、7 以上かつ 11 以下であるため Arr1[] をソートできるのは 8、9、10 の3つです。この中で最大なのは 10 です。

置き換え後の Arr1[] は { 1,3,5,7,10,11 } となり、正しく昇順にソートされます。

入力例 2

Arr1[]= { 12,5,22,17 }, Arr2[]= { 4,8,7,10,9 }

出力例 2

該当する要素は存在しません。

解説: Arr2[] には 12 以上 22 以下の要素が一つも存在しないため、Arr1[] をソート済みの状態にすることはできません。

アルゴリズムのアプローチ

• 配列 arr1[] と arr2[] に数値を格納します。arr1[] は昇順にソートされていますが、一つの要素だけが正しい位置にありません。
• 関数 sortMax( int arr1[], int arr2[], int n1, int n2 ) は両方の配列とその長さを受け取り、arr2[] 内に arr1[] の誤った要素を置き換えられる最大の要素が見つかった場合に arr1[] を更新します。
• 変数 wpos に、arr1[] 内で誤って配置された要素のインデックスを保存します。初期値は -1 です。
• 変数 maxx は、arr1[] の誤った要素を置き換えてソート状態にできる arr2[] の要素の中で最大のものを保存するために使用します。
• まず arr1[] を走査し、arr[i] < arr[i-1] となる不正な要素を見つけたら、そのインデックス i を wpos に保存します。
• 次に arr2[] を走査し、arr1[wpos-1] と arr1[wpos+1] の間に収まる要素を探します。該当する要素が存在すれば、それを現在の maxx と比較します。
• より大きい値が見つかるたびに maxx を更新していきます。
• 最後に arr1[wpos] を maxx で置き換えます。
• 該当する要素が見つかれば maxx を返し、見つからなければ -1 を返します。
• 要素が見つからなかった場合は、その旨のメッセージを表示します。
• 見つかった場合は、置き換え後のソート済み arr1[] を出力します。

このアルゴリズムは各配列をそれぞれ一度だけ走査するため、時間計算量は O(n1 + n2)、追加のメモリ使用量は O(1) と非常に効率的です。

C++ 実装例

// C++ program to make array sorted
#include <bits/stdc++.h>
using namespace std;
int sortMax(int arr1[], int arr2[], int n1, int n2) //making arr1 sorted{
    int wpos=-1;
    int maxx=-1;
    int i,j;
    for(i=0;i<n1;i++)
    if(arr1[i]<arr1[i-1])
       wpos=i;
    for(j=0;j<n2;j++){
        if(arr2[j]>=arr1[wpos-1] && arr2[j]<=arr1[wpos+1])
            if(arr2[j]>=maxx)
               maxx=arr2[j];
    }
    if(maxx!=-1)
        arr1[wpos]=maxx;
    return maxx;
}
int main(){
    int arr1[] = { 1, 3, 7, 4, 10 };
    int arr2[] = { 2, 1, 6, 8, 9 };
    int len1 = sizeof(arr1) / sizeof(arr1[0]);
    int len2 = sizeof(arr2) / sizeof(arr2[0]);
    int res=sortMax(arr1, arr2, len1, len2);
    if(res==-1)
        cout<<"No swap possible! No such element!";
    else{
        cout<<"Maximum in arr2[] to make arr1[] sorted:"<<res;
        cout<<endl<<"Arr1[]:";
        for(int i=0;i<len1;i++)
            cout<<arr1[i]<<" ";
            cout<<endl<<"Arr2[]:";
        for(int i=0;i<len2;i++)
            cout<<arr2[i]<<" ";
    }
}

実行結果

Maximum in arr2[] to make arr1[] sorted:9
Arr1[]:1 3 7 9 10
Arr2[]:2 1 6 8 9

この例では、arr1[] = { 1, 3, 7, 4, 10 } の中で「4」が誤った位置にある要素です。arr2[] の中で 3 以上 10 以下に収まる要素のうち最大の「9」を選ぶことで、arr1[] は { 1, 3, 7, 9, 10 } と正しくソートされます。