C ++での最大値と最小値の差を追加、削除、および返すためのクエリ

この問題では、Qクエリが与えられます。これらは3つのタイプで、-

• クエリ1：リストに番号Nを追加します。

• クエリ2：リストから番号Nを削除します。

• クエリ3：リストの最小要素と最大要素の差を返します。

私たちのタスクは、C ++の最大値と最小値の差を追加、削除、および返すクエリを解決するプログラムを作成することです。

問題の説明

リストで実行するクエリのQ個が与えられます。リストの最大要素と最小要素の違いを追加、削除、および検索するクエリには3つのタイプがあります。これを使用して、最初に要素のリストを作成し、次にリストの最大要素と最小要素の差のクエリ3値を見つけます。

問題を理解するために例を見てみましょう

入力 ：Q =6

クエリ（1、4）

クエリ（1、9）

クエリ（1、6）

クエリ（2、4）

クエリ（1、3）

クエリ（3）

出力 ：6

説明

最終的に、リストは{9、6、3}になります。

最大->9

最小->3

違い->6

ソリューションアプローチ

問題を解決するための簡単なアプローチは、各クエリの直接解決を使用することです。これらの手順に従うことによって-

• アレイを初期化します。

• クエリタイプ1の場合、配列に要素を追加します

• クエリタイプ2の場合、配列から要素を削除します

• クエリタイプ3の場合、最大値と最小値の差を見つけて、値を返します。

例

#include <iostream>
using namespace std;
void solveQuerry(int type, int item){
   int list[100];
   static int index = 0;
   if(type == 1){
      list[index] = item;
      index++;
   }
   else if(type == 2){
      for(int i = 0; i <= index; i++)
      if(list[i] == item ){
         list[i] = 0;
         break;
         }
      }
      else if(type == 3){
         int max = -100, min = 100;
      for(int i = 0; i< index; i++){
         if(list[i] == 0)
            i++;
         if(list[i] > max)
            max = list[i];
         if(list[i] < min)
            min = list[i];
      }
   cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
   }
}
int main() {
   int Q = 6;
   int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
   for(int i = 0; i< Q; i++){
      solveQuerry(query[i][0], query[i][1]);
   }
}

出力

The difference between the maximum and minimum elements of the list is 6

単純な配列よりも他のデータ構造を使用すると、検索プロセスがより効果的になる可能性があります。ここで、配列の代わりに自己平衡二分探索木を使用するとします。 max要素は最後になります（rbegin（）メソッドを使用してアクセスします）。そして、min要素が先頭になります（begin（）メソッドを使用してアクセスします）。

C ++での自己平衡二分探索木の実装は、セットを使用して行われます。

例

#include <bits/stdc++.h>
using namespace std;
set<int> myList;
void solveQuerry(int type, int num){
   if(type == 1){
      myList.insert(num);
   }
   else if(type == 2){
      myList.erase(num);
   }
   else if(type == 3){
      int max = *(myList.rbegin());
      int min = *(myList.begin());
      cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
   }
}
int main() {
   int Q = 6;
   int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
   for(int i = 0; i< Q; i++){
      solveQuerry(query[i][0], query[i][1]);
   }
}

出力

The difference between the maximum and minimum elements of the list is 6