C++ でソート ツリーをマージする

整数配列、セグメントの開始ポインターと終了ポインターのセット、およびキー値が与えられます。ここでの問題は、指定された範囲内のすべての値を見つけることです。指定されたキー値以下です。

例で理解しましょう

入力 - arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }

セグメント 1: 開始 = 2、終了 = 4、k = 2

セグメント 2: 開始 = 1、終了 = 6、k = 3

出力 - 指定された範囲内のキー値以下の数値の数は 2 です。 6

説明 - [8, 1, 4] は、範囲は 2 ～ 4 で、2 は範囲内で 2 番目に小さい数値です。 [7, 8, 1, 4, 6, 8] は 1 から 6 までの範囲を表します。6 は範囲内で 3 番目に小さい数値です。

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

段落 1: 開始位置 = 3、終了位置 = 6、k=4

段落 2: 開始位置 = 2 、終了Position=5、k=3

出力 - 指定された範囲内のキー値以下の数値の数は次のとおりです: 9 7

説明 - [9, 4, 6, 5] は 3 ～ 6 の範囲を表し、9 は指定された範囲内で 4 番目に小さい数値です。 [7, 9, 4, 6] は 2 から 4 までの範囲を表します。7 は指定されたセグメント範囲内で 3 番目に小さい数値です。

## 次のプログラムで使用されるメソッドは次のとおりです。

• 整数型の配列を宣言します。配列のサイズを計算します。整数型のペアを形成するベクトル型の変数を宣言します。 FOR ループを開始して、配列からベクトルにデータをプッシュします。

• 指定されたベクトルを並べ替えます。サイズが MAX の整数型のベクトル配列を作成します。

• 関数generateTree(1, 0, size - 1, vec, Tree)を呼び出し、getSmallestIndexをqueryWrapper(2, 5, 2, size, vec, Tree)に設定します。

• 入力[getSmallestIndex]を出力します。

• 関数 queryWrapper(1, 6, 4, size, vec,tree) を呼び出すように getSmallestIndex を設定します。

#関数内generateTree(int TreeIndex, int leftIndex, int rightIndex, Vector > &a, Vector Tree[])

• IF leftIndex を rightIndex にチェックし、設定します tree[treeIndex].push_back(a[leftIndex].second) および return
  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 Tree[])

• startIndex から endIndex までの IF をチェックして、tree[treeIndex][0 を返します] ]
  mid を (startIndex endIndex) / 2 に設定し、last_in_query_range を (upper_bound(tree[2 *treeIndex].begin(),tree[2 *treeIndex].end(), queryEnd) - ツリー[2 * ツリーインデックス].begin())
  first_in_query_range を ( lower_bound(tree[2 * ツリーインデックス].begin(),tree[2 * ツリーインデックス] に設定します。 end(), queryStart) - Tree[2 * TreeIndex].begin()) と M から last_in_query_range - first_in_query_range
  M が key より大きいかどうかを確認し、calculateKSmallest(startIndex, Mid, queryStart,queryEnd, 2 *treeIndex, key,tree)
  ELSE、次に、calculateKSmallest(mid 1, endIndex, queryStart, queryEnd, 2 *treeIndex 1, key - M,関数 int queryWrapper(int queryStart, int queryEnd, int key, int n, Vector > > &a) 内、vectortree[])
  関数 CalculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, Tree) の呼び出しを返す

• 例

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

    出力

  上記のコードを実行すると、次の出力が生成されます

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

以上がC++ でソート ツリーをマージするの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。