Rechercher l'index de début et de fin des éléments dans un tableau non trié en C++

Dans ce problème, nous obtenons un tableau aar[] contenant n valeurs entières non triées et une valeur entière. Notre tâche est de trouver l'index de début et de fin d'un élément dans un tableau non trié.

Pour les occurrences d'un élément dans le tableau, nous renverrons

"index de début et index de fin" (s'il est trouvé deux fois ou plus dans le tableau).

"index unique" s'il est trouvé

"élément non présent" s'il n'est pas présent dans le tableau.

Prenons un exemple pour comprendre le problème,

Exemple 1

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

Explication

L'élément 2 apparaît deux fois,

première fois à index = 0,

deuxième fois à index = 5

Exemple 2

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

Explication

L'élément 5 n'apparaît qu'une seule fois à l'index = 2,

Exemple 3

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

Solution

Un moyen simple de résoudre ce problème consiste à parcourir le tableau.

Nous allons parcourir le tableau et conserver deux valeurs d'index : la première et la dernière. Le premier index parcourra le tableau depuis le début et le dernier index parcourra depuis la fin du tableau. La boucle se termine lorsque les éléments du premier et du dernier index ont la même valeur.

Algorithme

• Étape 1 - Parcourez le tableau

  • Étape 1.1 - Utilisez le premier index pour parcourir depuis le début et le dernier index pour parcourir depuis la fin.

  • Étape 1.2 - Si la valeur à n'importe quel index est égale à val. N'augmentez pas la valeur de l'indice.

  • Étape 1.3 - Retourne si les deux index ont la même valeur.

Exemple

Programme qui illustre le fonctionnement de notre solution

#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;
}

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!