C++ 프로그램에서 L번째 가장 작은 숫자와 R번째 가장 작은 숫자 사이의 절대 차이를 반환하는 쿼리

이 문제에서 크기가 n인 배열 arr[]이 주어지고 각각 2개의 값 L과 R로 구성된 Q 쿼리가 제공됩니다. 우리의 임무는 L번째 가장 작은 숫자와 R번째로 작은 숫자입니다.

문제 설명 − 각 쿼리를 해결하려면 L번째로 작은 숫자와 R번째로 작은 숫자의 인덱스를 찾아야 합니다. 그리고 이 지수들의 차이를 찾으세요.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력

arr[] = {8, 4, 1, 5, 2} Q = 2 Queries[][] = {{2, 4}, {1, 5}}

출력

1 2

설명

For {2, 4}: 2nd smallest element is 2 whose index is 4
4th smallest element is 5 whose index is 3 Difference = 4 - 3 = 1
For {1, 5} Smallest element is 1 whose index is 2
5th smallest element is 8 whose index is 0 Difference = 2 - 0 = 2

솔루션 접근 방식

문제를 해결하기 위해 배열 요소의 인덱스와 값을 저장할 쌍을 만듭니다. 그리고 각 쿼리의 L 값과 R 값 모두에 대해 i 번째로 작은 요소를 찾습니다. 그런 다음 인덱스의 절대 차이를 인쇄합니다.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <bits/stdc++.h>
using namespace std;
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
   pair<int, int> arrayIndex[n];
   for (int i = 0; i < n; i++) {
      arrayIndex[i].first = arr[i];
      arrayIndex[i].second = i;
   }  
   sort(arrayIndex, arrayIndex + n);
   for (int i = 0; i < Q; i++){
      int result = ( abs(arrayIndex[queries[i][0] - 1].second - arrayIndex[queries[i][1] - 1].second) );
      cout<<"For Query "<<(i+1)<<": Difference is "<<result<<endl;
   }
}
int main() {
   int arr[] = { 8, 4, 1, 5, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
   solveAllQueries(arr, n, Q, queries);
   return 0;
}

출력

For Query 1: Difference is 1
For Query 2: Difference is 2

이 프로그램은 쌍 데이터 구조를 사용하지만 사용하지 않고 차이를 찾을 수 있는 솔루션이 있습니다. 이를 위해 요소를 오름차순으로 저장할 배열을 사용할 것입니다. 그런 다음 각 쿼리에 대해 L 및 R 값 모두에 대해 i번째 가장 작은 요소를 찾습니다. 그런 다음 지수의 차이를 찾으십시오.

우리 솔루션의 작동을 설명하는 프로그램

예시

#include <bits/stdc++.h>
using namespace std;
int searchEle(int arr[], int ele, int n){
    for(int i = 0; i < n; i++)
   if(arr[i] == ele)
      return i;
      return -1;
}
int findDifference(int arr[], int minArray[], int n, int L, int R){
   int Lele = minArray[L-1];
   int Rele = minArray[R-1];
   int index1 = searchEle(arr, Lele, n);
   int index2 = searchEle(arr, Rele, n);
   return abs(index1 - index2);
 }
void solveAllQueries(int arr[], int n,int Q, int queries[][2] ) {
   int minArray[n];
   for (int i = 0; i < n; i++)
   minArray[i] = arr[i];
   sort(minArray, minArray + n);
   for(int i = 0; i < Q; i++){
      cout<<"For Query "<<(i+1)<<": Difference is "<<findDifference(arr, minArray, n,       queries[i][0], queries[i][1])<<endl;
   }
}
int main() {
   int arr[] = { 8, 4, 1, 5, 2 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int Q = 2; int queries[][2] = { { 2, 4 }, { 1, 5 }};
   solveAllQueries(arr, n, Q, queries); return 0;
}

출력

For Query 1: Difference is 1
For Query 2: Difference is 2