En C++, retrouver l'index du pointeur gauche dans un tableau après un éventuel déplacement

Dans cette question, on nous donne un tableau arr[] de taille N. Notre tâche est de trouver l'index du pointeur gauche après d'éventuels déplacements dans le tableau.

Nous avons deux pointeurs, l'un est le pointeur gauche et l'autre est le pointeur droit.

Le pointeur gauche commence à l'indice 0 et augmente en valeur.

Le pointeur droit part de l'index (n-1) et la valeur diminue.

Si la somme des pointeurs gauche est inférieure à la somme des pointeurs droits, la valeur du pointeur est augmentée, sinon la valeur du pointeur est diminuée. Et la valeur de la somme sera mise à jour.

Comprenons ce problème à travers un exemple, la traduction chinoise de

Input : arr[] = {5, 6, 3, 7, 9, 4}
Output : 2

Explication −

est :

Explication −

leftPointer = 0 -> sum = 5, rightPointer = 5 -> sum = 4. Move rightPointer
leftPointer = 0 -> sum = 5, rightPointer = 4 -> sum = 13. Move leftPointer
leftPointer = 1 -> sum = 11, rightPointer = 4 -> sum = 13. Move leftPointer
leftPointer = 2 -> sum = 14, rightPointer = 4 -> sum = 13. Move rightPointer
leftPointer = 2 -> sum = 14, rightPointer = 3 -> sum = 20. Move rightPointer
Position of the left pointer is 2.

Solution

En déplaçant les pointeurs gauche et droit en fonction de la taille de la somme pour résoudre le problème. Vérifiez ensuite si le pointeur gauche est supérieur de 1 au pointeur droit.

Exemple

Exemple de programme illustrant le fonctionnement de notre solution

#include <iostream>
using namespace std;
int findIndexLeftPointer(int arr[], int n) {
   if(n == 1)
      return 0;
   int leftPointer = 0,rightPointer = n-1,leftPointerSum = arr[0], rightPointerSum = arr[n-1];
   while (rightPointer > leftPointer + 1) {
      if (leftPointerSum < rightPointerSum) {
         leftPointer++;
         leftPointerSum += arr[leftPointer];
      }
      else if (leftPointerSum > rightPointerSum) {
         rightPointer--;
         rightPointerSum += arr[rightPointer];
      }
      else {
         break;
      }
   }
   return leftPointer;
}
int main() {
   int arr[] = { 5, 6, 3, 7, 9, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The index of left pointer after moving is "<<findIndexLeftPointer(arr, n);
   return 0;
}

Sortie

The index of left pointer after moving is 2

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!