資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++程式中返回第 L 小數和第 R 小數的絕對差的查詢
在這個問題中，我們給定一個大小為 n 的陣列 arr[] 和 Q 個查詢，每個查詢包含 2 個值 L 和 R。我們的任務是建立一個程式來解決查詢，以返回第 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
此程式使用 pair 資料結構，但有一種解決方案可以在不使用它的情況下找到差異。為此，我們將使用一個數組，該陣列將按升序儲存元素。然後為每個查詢的 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
更新於: 2020-12-22
77 次檢視
廣告