資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中陣列元素在給定範圍內的計數查詢
在這個問題中，我們給定一個數組 arr[] 和 Q 個查詢，每個查詢可以是以下兩種型別之一，
{1, L, R} - 查詢範圍 [L, R] 內的陣列元素個數。
{2, index, val} - 將索引處的元素更新為 val。
我們的任務是建立一個程式，用 C++ 解決陣列元素在給定範圍內的計數查詢。
讓我們舉一個例子來理解這個問題，
輸入:arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3}
Q = 3
查詢 = { {1, 4, 8},
{2, 6, 5},
{1, 1, 4}}
輸出:3 7
解釋
查詢 1：計算範圍 [4, 8] 內的陣列元素個數。個數 = 1
查詢 2：更新元素 arr[6] = 5。新的陣列，arr[] = {1, 5, 2, 4, 2, 2, 5, 1, 3}
查詢 1：計算範圍 [4, 8] 內的陣列元素個數。個數 = 7
解決方案方法
解決這個問題的一個簡單方法是直接遍歷陣列，並找到所有在範圍內的元素，即 L =< 元素 =< R。
示例
#include <iostream>
using namespace std;
int countElementInRange(int arr[], int N, int L, int R){
int ValueCount = 0;
for (int i = 0; i < N; i++) {
if (arr[i] >= L && arr[i] <= R) {
ValueCount++;
}
}
return ValueCount;
}
int main() {
int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
int N = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is " <<countElementInRange(arr,N, query[i][1], query[i][2])<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
}輸出
The count of array elements with value in given range is 2 Updating Value The count of array elements with value in given range is 7
該解決方案方法需要對每個迴圈進行一次迭代。因此，其時間複雜度為 O(Q*N)。
解決這個問題的一個更好的方法是使用二叉索引樹或 Fenwick 樹資料結構。在這裡，我們將陣列的元素儲存在樹中，這將使我們能夠使用陣列元素作為索引。我們可以輕鬆地使用 getSum 函式（該函式是資料結構的內建函式）找到範圍內的元素個數。
ElementCount[L, R] = getSum(R) - getSum(L - 1)
示例
#include <iostream>
using namespace std;
class BinaryIndTree {
public:
int* BIT;
int N;
BinaryIndTree(int N) {
this->N = N;
BIT = new int[N];
for (int i = 0; i < N; i++) {
BIT[i] = 0;
}
}
void update(int index, int increment) {
while (index < N) {
BIT[index] += increment;
index += (index & -index);
}
}
int calcSum(int index) {
int sum = 0;
while (index > 0) {
sum += BIT[index];
index -= (index & -index);
}
return sum;
}
};
void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree*fenwickTree){
int removedElement = arr[index];
fenwickTree->update(removedElement, -1);
arr[index] = val;
fenwickTree->update(val, 1);
}
int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree*
fenwickTree) {
return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}
int main() {
int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
int Q = 3;
int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
int N = 100001;
BinaryIndTree* fenwickTree = new BinaryIndTree(N);
for (int i = 0; i < n; i++)
fenwickTree->update(arr[i], 1);
for(int i = 0; i < Q; i++){
if(query[i][0] == 1)
cout<<"The count of array elements with value in given range is "<<countElementInRange(arr, n, query[i][1], query[i][2],fenwickTree)<<endl;
else if(query[i][0] == 2){
cout<<"Updating Value \n";
UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
}
}
return 0;
}輸出
The count of array elements with value in given range is 2 Updating Value The count of array elements with value in given range is 7
更新於: 2020年10月9日
524 次檢視
廣告