Sortierbaum in C++ zusammenführen

Wir erhalten ein ganzzahliges Array, eine Reihe von Segmentanfangs- und -endzeigern sowie einen Schlüsselwert. Die Problemstellung besteht hier darin, alle Werte im angegebenen Bereich zu finden, die kleiner oder gleich dem angegebenen Schlüssel sind Wert.

Lassen Sie es uns anhand eines Beispiels verstehen

Eingabe − arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }

Segment 1: Start = 2, Ende = 4, k = 2

Segment 2: Start = 1, Ende = 6, k = 3

Ausgabe − Anzahl der Zahlen, die kleiner oder gleich dem Schlüsselwert im angegebenen Bereich sind, sind 2 6

Erklärung − [8, 1, 4] stellt den Bereich von 2 bis 4 dar und 2 ist die zweitkleinste Zahl im Bereich [7, 8, 1, 4, 6, 8] stellt den Bereich von 1 bis 6 dar, 6 ist die drittkleinste Zahl im Bereich

Eingabe - arr[] = {2, 7, 9, 4, 6 , 5 , 1 |

Absatz 1: Startposition=3, Endposition=6, k=4

Absatz 2: Startposition=2, Endposition=5, k=3

Ausgabe - in Die Zahl Anzahl der Zahlen kleiner oder gleich dem Schlüsselwert im angegebenen Bereich ist: 9 7

Erklärung – [9, 4, 6, 5] stellt den Bereich von 3 bis 6 dar, 9 ist der viertkleinste im angegebenen Bereich Nummer [7, 9, 4, 6] stellt den Bereich von 2 bis 4 dar, 7 ist die drittkleinste Zahl im angegebenen Segmentbereich

Die im folgenden Programm verwendete Methode ist wie folgt:

• Deklarieren Sie ein Array von Ganzzahlen Typ. Berechnen Sie die Größe des Arrays. Deklarieren Sie eine Variable vom Typ Vektor und bilden Sie ein Paar ganzzahliger Typen. Starten Sie eine FOR-Schleife, um Daten aus dem Array in den Vektor zu übertragen.

• Sortieren Sie den angegebenen Vektor. Erstellen Sie ein Vektorarray vom Typ Integer mit der Größe MAX.

• Rufen Sie die Funktion genericTree(1, 0, size - 1, vec, tree) auf und setzen Sie getSmallestIndex auf queryWrapper(2, 5, 2, size, vec, tree).

• Eingabe drucken[getSmallestIndex].

• Setzen Sie getSmallestIndex, um die Funktion queryWrapper(1, 6, 4, size, vec, tree) aufzurufen. 🔜 Satz tree[treeIndex].push_back(a[leftIndex].second) und return

• Setze midValue auf (leftIndex + rightIndex) / 2 und rufe genericTree(2 * treeIndex, leftIndex, midValue, a, tree) auf, genericTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) und merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin( ).Setze tree[2 * treeIndex + 1].end(),back_inserter(tree[treeIndex]))

  Innerhalb der Funktion als int berechneKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[])
  Überprüfen Sie IF startIndex bis endIndex und geben Sie dann tree[treeIndex][0] zurück

• Mitte auf (startIndex + endIndex) / 2 setzen, last_in_query_range auf (upper_bound(tree[ 2 * treeIndex].begin(),tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin())

  • setze first_in_query_range auf (lower_bound(tree[2 * treeIndex] .begin(),tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) und M zu last_in_query_range - first_in_query_range

  • Überprüfen Sie, ob M größer als gleich ist, und geben Sie dann den Schlüssel zurück berechneKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree)

  • ELSE, dann zurück berechneKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree) .

  Innerhalb der Funktion int queryWrapper(int queryStart, int queryEnd, int key, int n, vector > &a, vectortree[])
  return Aufruf der Funktion berechneKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree)

• Beispiel

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

    Ausgabe

  Wenn wir den obigen Code ausführen, wird die folgende Ausgabe angezeigt generiert werden

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

Das obige ist der detaillierte Inhalt vonSortierbaum in C++ zusammenführen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!