查询以返回C ++程序中第L个最小数字与第R个最小数字之间的绝对差

在这个问题中，我们为数组arr []设置了大小为n和Q的查询，每个查询均由2个值L和R组成。我们的任务是创建一个程序来求解查询，以返回第L个最小数字与第L个最小数字之间的绝对差第R个最小数字。

问题描述-为了解决每个查询，我们需要找到最小Lth和最小Rth的索引。并找出这些指数之间的差异。

让我们举个例子来了解这个问题，

输入值

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<<"查询 "<<(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;
}

输出结果

查询 1: Difference is 1
查询 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<<"查询 "<<(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;
}

输出结果

查询 1: Difference is 1
查询 2: Difference is 2