数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告