C++でソートされていない配列内の要素の開始インデックスと終了インデックスを検索します

この問題では、ソートされていないn個の整数値と整数値の配列aar[]が与えられます。私たちのタスクは、並べ替えられていない配列内の要素の開始インデックスと終了インデックスを見つけることです 。

配列内の要素の出現については、

"開始インデックスと終了インデックス" アレイで2回以上見つかった場合。

"単一のインデックス" 配列内で1回見つかった場合。

"要素が存在しません" アレイに存在しない場合。

問題を理解するために例を見てみましょう

例1

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 2
Output : starting index = 0, ending index = 5

説明

要素2には2つのオカレンスがあります。
最初にインデックス=0で、
インデックス=5で2番目

例2

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 5
Output : Present only once at index 2

説明

インデックス=2で、要素5の出現は1つだけです

例3

Input : arr[] = {2, 1, 5, 4, 6, 2, 3}, val = 7
Output : Not present in the array!

ソリューションアプローチ

この問題の簡単な解決策は、アレイをトラバースすることです。

配列をトラバースし、最初と最後の2つのインデックス値を保持します。最初のインデックスは最初から配列をトラバースし、最後のインデックスは最後から配列をトラバースします。そして、最初と最後のインデックスの要素の値が同じになったら、ループを終了します。

アルゴリズム

• ステップ1 −アレイをループする

  • ステップ1.1 −開始からのトラバースには最初のインデックスを使用し、終了からのトラバースには最後のインデックスを使用します。

  • ステップ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