Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 배열의 최소-최대 범위 쿼리

<시간/>

N개의 요소를 포함하는 배열 Arr[]이 제공됩니다. 목표는 쿼리의 인덱스에서 최소값과 최대값을 찾는 것입니다.

쿼리에 따라 시작 인덱스와 끝 인덱스가 제공됩니다.

예

에서 - Arr[] ={ 1, 2, 3, 4, 5 } QStart =1 QEnd =4

밖으로 -

최소값 :2

최대값 :5

설명 −위 쿼리에서 시작 인덱스는 1이고 끝 인덱스는 4입니다. 이 두 인덱스 사이에서 Arr의 최소값은 2이고 최대값은 5입니다.

에서 - Arr[] ={ 10, 12, 3, 2, 5, 18 } QStart =2 QEnd =5

밖으로 -

최소값 :2

최대값 :18

설명 − 위 쿼리에서 시작 인덱스는 2이고 끝 인덱스는 5입니다. 이 두 인덱스 사이에서 Arr의 최소값은 2이고 최대값은 18입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다 -

이 접근 방식에서 우리는 주어진 쿼리 범위에서 최소값과 최대값을 찾기 위해 lpos에서 rpos까지의 범위에 대한 세그먼트 트리를 사용할 것입니다.

  • 입력 배열 Arr[]과 쿼리 인덱스 QStart 및 QEnd를 사용합니다.

  • 유형 값의 결과를 가져옵니다.

  • 구조체 값은 주어진 쿼리를 사용하여 배열에서 찾은 최소값과 최대값을 저장하는 데 사용됩니다.

  • 구조체 값은 주어진 쿼리를 사용하여 배열에서 찾은 최소값과 최대값을 저장하는 데 사용됩니다.

  • 함수 minMax(구조체 값 *root1, int num, int qStart1, int qEnd1)은 쿼리 인덱스를 사용하고 인덱스 범위 qStart1과 qEnd1 사이의 배열에서 최소값과 최대값을 찾습니다.

  • ( qStart1 <0 OR qEnd1> num-1 OR qStart1> qEnd1 )인지 확인하십시오. true이면 쿼리의 입력 범위가 유효하지 않습니다.

  • 그렇지 않으면 minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0)를 호출합니다.

  • 함수 minmaxFind(구조체 값 *root, int startT, int endT, int qStart, int qEnd, int pos)는 재귀 함수입니다. 현재 값의 시작 및 끝 인덱스를 startT 및 endT로 세그먼트 트리 루트에 대한 포인터가 필요합니다.

  • 또한 쿼리 범위에서 시작 및 끝 인덱스를 사용합니다. 세그먼트 트리의 현재 값 인덱스에는 인덱스 위치가 있습니다.

  • (qStart <=startT) AND if( qEnd>=endT)인 경우 현재 값의 세그먼트는 지정된 범위의 일부입니다. 따라서 해당 값의 최소값과 최대값을 반환합니다.

  • 범위를 벗어나면 현재 값을 minVal 및 maxVal로 업데이트합니다.

  • 현재 부분이 주어진 범위와 겹치면 :-

  • midl =startT + ( endT - startT )/2를 취하십시오.

  • p1과 p2를 2*pos+1 및 =2*pos+2로 취합니다.

  • lpos를 lpos =minmaxFind(root, startT, middl, qStart, qEnd, p1)로 업데이트하고 rpos를 minmaxFind(root, middl+1, endT, qStart, qEnd, p2)로 업데이트합니다.

  • temp.minVal을 lpos.minVal 및 rpos.minVal의 최소값으로 설정합니다.

  • temp.maxVal을 lpos.maxVal 및 rpos.maxVal의 최대값으로 설정합니다.

  • 반환 온도.

  • 함수 segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2)는 인덱스 범위가 startT2 및 endT2이고 현재 값 위치가 pos2인 배열 arr2[]에 대한 세그먼트 트리를 구성하는 데 사용됩니다.

  • 함수 *createTree(int arr0[], int num0)는 주어진 배열 arr0에서 세그먼트 트리를 구성하는 데 사용됩니다. 이 함수는 세그먼트 트리에 메모리를 할당하고 메모리 할당을 위해 segmentTree()를 호출합니다.

예

#include<bits/stdc++.h>
using namespace std;
struct value{
   int minVal;
   int maxVal;
};
struct value minmaxFind(struct value *root, int startT, int endT, int qStart,
   int qEnd, int pos){
   struct value temp, lpos ,rpos;
   if (qStart <= startT) {
      if( qEnd >= endT)
         { return root[pos]; }
   }
   if (endT < qStart || startT > qEnd) {
      temp.minVal = 9999;
      temp.maxVal = -9999;
      return temp;
   }
   int middl = startT + ( endT - startT )/2;
   int p1=2*pos+1;
   int p2=2*pos+2;
   lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1);
   rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2);
   temp.minVal = (lpos.minVal<rpos.minVal) ? lpos.minVal : rpos.minVal ;
   temp.maxVal = (lpos.maxVal>rpos.maxVal) ? lpos.maxVal : rpos.maxVal ;
   return temp;
}
struct value minMax(struct value *root1, int num, int qStart1, int qEnd1){
   struct value temp1;
   if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1){
      cout<<"Please enter Valid input!!";
      temp1.minVal = 9999;
      temp1.maxVal = -9999;
      return temp1;
   }
   return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}
void segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2){ 
   if (startT2 == endT2) { 
      root2[pos2].minVal = arr2[startT2];
      root2[pos2].maxVal = arr2[startT2];
      return ;
   }
   int p1=pos2*2+1;   
   int p2=pos2*2+2;
   int middl2 = startT2+(endT2-startT2)/2;
   segmentTree(arr2, startT2, middl2, root2, p1);
   segmentTree(arr2, middl2+1, endT2, root2, p2);
   root2[pos2].minVal = root2[p1].minVal<root2[p2].minVal ? root2[p1].minVal : root2[p2].minVal;
   root2[pos2].maxVal = root2[p1].maxVal>root2[p2].maxVal ? root2[p1].maxVal : root2[p2].maxVal;
}
struct value *createTree(int arr0[], int num0) { 
   int height = (int)(ceil(log2(num0)));
   int maxS = 2*(int)pow(2, height) - 1;
   struct value *root0 = new struct value[maxS];
   segmentTree(arr0, 0, num0-1, root0, 0);
   return root0;
}
int main() { 
   int Arr[] = { 1, 2, 3, 4, 5 };
   int length = sizeof(Arr)/sizeof(Arr[0]);
   struct value *tree = createTree(Arr, length);
   int QStart = 1;
   int QEnd = 4;
   struct value answer=minMax(tree, length, QStart, QEnd);
   cout<<"Minimum Value : "<<answer.minVal<<endl;
   cout<<"Maximum Value : "<<answer.maxVal;
   return 0;
}

출력

위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Minimum Value : 2
Maximum Value : 5