C++でソートされていない配列内の要素の開始インデックスと終了インデックスを見つける方法

問題の概要

この問題では、ソートされていない n 個の整数値からなる配列 arr[] と整数 val が与えられます。求められているのは、ソートされていない配列の中で特定の要素が出現する開始インデックスと終了インデックスを見つけることです。

配列内での要素の出現状況に応じて、以下の結果を返します。

• 要素が配列内に2回以上出現する場合 →「開始インデックスと終了インデックス」を返す
• 要素が配列内に1回だけ出現する場合 →「単一のインデックス」を返す
• 要素が配列内に存在しない場合 →「要素は存在しません」と返す

具体例を使って問題を確認しましょう。

例1

入力 : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
出力 : 開始インデックス = 0, 終了インデックス = 5

説明

要素 2 は配列内に2回出現します。
1回目はインデックス 0、
2回目はインデックス 5 の位置です。

例2

入力 : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
出力 : インデックス 2 に1回だけ存在します

説明

要素 5 は配列内に1回だけ出現し、その位置はインデックス 2 です。

例3

入力 : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
出力 : 配列内に存在しません!

解決アプローチ

この問題に対するシンプルな解決策は、配列を走査することです。

配列を走査する際に、first(先頭用)と last(末尾用)の2つのインデックスを管理します。first インデックスは配列の先頭から順に進み、last インデックスは配列の末尾から順に進みます。そして、両方のインデックスが指す要素の値が一致した時点でループを終了します。これにより、目的の要素が最初に出現する位置と最後に出現する位置を同時に特定できます。

アルゴリズム

• ステップ1 − 配列をループ処理します。
  • ステップ1.1 − first インデックスで先頭から、last インデックスで末尾からそれぞれ走査します。
  • ステップ1.2 − あるインデックス位置の値が val と等しい場合は、そのインデックスをそれ以上移動させません。
  • ステップ1.3 − 両インデックスが指す値が一致した場合、結果を返して処理を終了します。

実装例

この解決策の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

void findStartAndEndIndex(int arr[], int n, int val) {
    int start = 0;
    int end = n - 1;
    while(1){
    if(arr[start] != val)
        start++;
    if(arr[end] != val)
        end--;
    if(arr[start] == arr[end] && arr[start] == val)
        break;
    if(start == end)
        break;
}
    if (start == end ){
        if(arr[start] == val)
            cout<<"Element is present only once at index : "<<start;
        else
            cout<<"Element Not Present in the array";
    } else {
        cout<<"Element present twice at \n";
        cout<<"Start index: "<<start<<endl;
      cout<<"Last index: "<<end;
   }
}
int main() {
   int arr[] = { 2, 1, 5, 4, 6, 2, 9, 0, 2, 3, 5 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int val = 2;
   findStartAndEndIndex(arr, n, val);
   return 0;
}

出力

Element present twice at
Start index: 0
Last index: 8