Maison > développement back-end > C++ > Rechercher l'index de début et de fin des éléments dans un tableau non trié en C++

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

WBOY
Libérer: 2023-08-29 10:17:06
avant
1047 Les gens l'ont consulté

Rechercher lindex 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
Copier après la connexion

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
Copier après la connexion

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!
Copier après la connexion

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.

    • < /ul>

    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;
    }
    Copier après la connexion

    Sortie

    Element present twice at
    Start index: 0
    Last index: 8
    Copier après la connexion

    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!

Étiquettes associées:
source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal