C++에서 최대값과 최소값의 차이를 추가, 제거 및 반환하는 쿼리

<시간/>

이 문제에서는 Q 쿼리가 제공됩니다. 세 가지 유형이 있으며 다음과 같습니다. -

쿼리 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