Fusionner l'arborescence de tri en C++

Nous recevons un tableau d'entiers, un ensemble de pointeurs de début et de fin de segment et une valeur clé et l'énoncé du problème ici est de trouver toutes les valeurs dans la plage donnée qui sont inférieures ou égales à la clé donnée valeur.

Comprenons avec un exemple

Entrée − arr[] = {7, 8, 1, 4, 6, 8, 10 }

Segment 1 : début = 2, fin = 4, k = 2.

Segment 2 : début = 1, fin = 6, k = 3

Sortie − Le nombre de nombres inférieurs ou égaux à la valeur clé dans la plage donnée est 2 6

Explication − [8, 1, 4] représente la plage de 2 à 4 et 2 est le 2ème plus petit nombre de la plage [7, 8, 1, 4, 6, 8] représente la plage de 1 à 6, 6 est le troisième plus petit nombre de la plage

Entrée - arr[] = {2, 7, 9, 4, 6 , 5 , 1 |

Paragraphe 1 : position de départ=3, position de fin=6, k=4

Paragraphe 2 : position de départ=2, position de fin=5, k=3

Sortie - dans Le nombre de nombres inférieurs ou égaux à la valeur clé dans la plage donnée est : 9 7

Explication - [9, 4, 6, 5] représente la plage de 3 à 6, 9 est le quatrième plus petit dans la plage donnée nombre [7, 9, 4, 6] représente la plage de 2 à 4, 7 est le 3ème plus petit nombre dans la plage de segments donnée

La méthode utilisée dans le programme suivant est la suivante :

• Déclarer un tableau d'entiers taper. Calculez la taille du tableau. Déclarez une variable de type vector, formant une paire de types entiers. Démarrez une boucle FOR pour pousser les données du tableau vers le vecteur.

• Triez le vecteur donné. Créez un tableau vectoriel de type entier de taille MAX.

• Appelez la fonction generateTree(1, 0, size - 1, vec, tree) et définissez getSmallestIndex sur queryWrapper(2, 5, 2, size, vec, tree).

• Imprimer l'entrée [getSmallestIndex].

• Définissez getSmallestIndex pour appeler la fonction queryWrapper (1, 6, 4, size, vec, tree).

• À l'intérieur de la fonction generateTree(int treeIndex, int leftIndex, int rightIndex, vector > &a, vector tree[])

  • vérifiez IF leftIndex à rightIndex, puis ensemble tree[treeIndex].push_back(a[leftIndex].second) et return

  • Définissez midValue sur (leftIndex + rightIndex) / 2et appelez generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) et merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin( ). Définissez tree[2 * treeIndex + 1].end(),back_inserter(tree[treeIndex]))

• À l'intérieur de la fonction comme int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, clé int, arbre vectoriel[])

  • Vérifiez SI startIndex à endIndex puis retournez tree[treeIndex][0]

  • Définissez mid sur (startIndex + endIndex) / 2, last_in_query_range à (upper_bound(tree[ 2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin())

  • définir first_in_query_range sur (lower_bound(tree[2 * treeIndex] .begin(),tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) et M à last_in_query_range - first_in_query_range

  • Vérifiez SI M supérieur à égal à la clé puis revenez calculateKSmallest(startIndex, mid, queryStart,queryEnd, 2 * treeIndex, key, tree)

  • ELSE, puis renvoie calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree) .

• À l'intérieur de la fonction int queryWrapper(int queryStart, int queryEnd, int key, int n, vector > &a, vectortree[])

  • return appel à la fonction calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

Example

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000;
void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]){
   if (leftIndex == rightIndex){
      tree[treeIndex].push_back(a[leftIndex].second);
      return;
   }
   int midValue = (leftIndex + rightIndex) / 2;
   generateTree(2 * treeIndex, leftIndex, midValue, a, tree);
   generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree);
   merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(),
   tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex]));
}
int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]){
      if (startIndex == endIndex){
         return tree[treeIndex][0];
      }
      int mid = (startIndex + endIndex) / 2;
      int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin());
      int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(),queryStart) - tree[2 * treeIndex].begin());
      int M = last_in_query_range - first_in_query_range;
      if (M >= key){
         return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree);
      }
      else {
         return calculateKSmallest(mid + 1, endIndex, queryStart,queryEnd, 2 * treeIndex + 1, key - M, tree);
      }
}
int queryWrapper(int queryStart, int queryEnd, int key, int n,
   vector<pair<int, int> > &a, vector<int> tree[]){
      return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree);
}
int main(){
   int input[] = { 7, 8 , 1, 4 , 6 , 8 , 10 };
   int size = sizeof(input)/sizeof(input[0]);
   vector<pair<int, int> > vec;
   for (int i = 0; i < size; i++) {
      vec.push_back(make_pair(input[i], i));
   }
   sort(vec.begin(), vec.end());
   vector<int> tree[MAX];
   generateTree(1, 0, size - 1, vec, tree);

   cout<<"Count of number which are smaller than or equal to key value in the given range are:"<<endl;

   int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree);
   cout << input[getSmallestIndex] << endl;
   getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree);
   cout << input[getSmallestIndex] << endl;
   return 0;
}

Output

Si nous exécutons le code ci-dessus, la sortie suivante sera être généré

Count of number which are smaller than or equal to key value in the given range are:
4
6

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!