C++でソート済み配列に含まれる余分な要素のインデックスを見つける方法

この問題では、サイズ n と n+1 の2つのソート済み配列 arr1 と arr2 が与えられます。両配列の要素は、余分な要素を除いてすべて同じです。私たちのタスクは、ソート済み配列の一方に存在する余分な要素のインデックスを見つけることです。

問題の説明： サイズ n+1 の配列に存在し、サイズ n の配列には存在しない要素のインデックスを求める必要があります。

問題を理解するための例

入力： arr1[n] = {3, 5, 7, 8, 9, 12}
　　　　arr2[n+1] = {3, 4, 5, 7, 8, 9, 12}

出力： 1

説明：

値が 4 の要素が余分な要素であり、そのインデックスは 1 です。

解決アプローチ

最もシンプルな解決策は、「両方の配列がソートされている」という性質を利用する方法です。異なる要素は1つだけであるため、線形探索を行うことで、arr1[] に存在しない arr2 の要素を簡単に見つけることができます。

アルゴリズム：

ステップ1： i を 0 から n+1 までループさせる。

ステップ1.1： 異なる要素、つまり arr1[i] != arr2[i] となる要素を見つけたら、ループを抜ける。

ステップ2： i の値を返す。

解決策の動作を示すプログラム

例

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {

    int i;
    for (i = 0; i < n; i++)
       if (arr1[i] != arr2[i])
          break;
    return i;
}

int main()
{
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
    return 0;
}

出力

The extra element is at index (1) and the value is 4

この解決策は、線形探索の代わりに、より効率的な探索手法である二分探索（バイナリサーチ）を使用することで改善できます。二分探索では、配列の中央にある要素同士を比較し、一致していれば探索範囲を右半分に、一致していなければ左半分に絞り込んでいくため、O(log n) の時間計算量で余分な要素を見つけることができ、アルゴリズムの計算時間を大幅に短縮できます。

二分探索を使った解決策のプログラム

例

#include <iostream>
using namespace std;

int findExtraElement(int arr1[], int arr2[], int n) {

    int extraIndex = n;
    int start = 0, end = n - 1;
    while (start <= end)
    {
        int mid = (start + end) / 2;
        if (arr2[mid] == arr1[mid])
            start = mid + 1;
        else
        {
            extraIndex = mid;
            end = mid - 1;
        }
    }
    return extraIndex;
}

int main()
{
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
    return 0;
}

出力

The extra element is at index (1) and the value is 4

別のアプローチ：合計の差を利用する方法

もう一つの解決方法として、2つの配列の合計値の差を求めるアプローチがあります。この差の絶対値こそが余分な要素の値です。次に、サイズ n+1 の配列の中から探索アルゴリズムを使ってこの余分な要素のインデックスを見つけます。この方法の時間計算量は O(n) となります。

合計の差を利用した解決策のプログラム

例

#include <iostream>
using namespace std;

int calcArraysum(int arr[], int n){
    int sum = 0;
    for(int i = 0; i < n; i++)
       sum += arr[i];
    return sum;
}

int findExtraElement(int arr1[], int arr2[], int n) {

    int extraValue = calcArraysum(arr2, n+1) - calcArraysum(arr1, n);

    for (int i = 0; i < n; i++)
    {
        if (arr2[i] == extraValue)
            return i;
    }
    return -1;
}

int main()
{
    int arr1[] = {3, 5, 7, 8, 9, 12};
    int arr2[] = {3, 4, 5, 7, 8, 9, 12};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    int extraIndex = findExtraElement(arr1, arr2, n);
    cout<<"The extra element is at index ("<<extraIndex<<") and the value is "<<arr2[extraIndex];
    return 0;
}

出力

The extra element is at index (1) and the value is 4