数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 查询区间内第 K 位设置的数组元素个数
在本文中，我们将讨论一个问题，即查找给定范围内具有第 k 位设置的元素数量，例如 -
Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
0
1我们将通过蛮力方法解决这个问题，并看看这种方法是否适用于更高的约束。如果不是，那么我们尝试思考一种新的有效方法。
蛮力方法
在这种方法中，我们将简单地遍历该范围并检查每个元素的第 k 位是否已设置，如果是，则增加计数。
示例
#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
if (n & (1 << (k - 1)))
return true;
return false;
}
int query(int L, int R, int K, int arr[]) {
int count = 0; // counter to keep count of number present in the range
for (int i = L; i <= R; i++) { // traversing the range
if (Kset(arr[i], K)) {
count++;
}
}
return count;
}
int main() {
int arr[] = { 4, 5, 7, 2 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int queries[][3] = { // given L, R and k
{ 2, 4, 4 },
{ 3, 5, 1 }
};
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K, arr) << "\n";
}
return 0;
}输出
0 1
上述方法的时间复杂度为 O(N*Q)，其中 N 是数组的大小，Q 是我们给定的查询数量；如您所见，这种方法不适用于更高的约束，因为它将花费太多时间，因此现在我们将尝试编写一个高效方法的程序。
高效方法
在这种方法中，我们将维护一个二维前缀和数组，该数组将保留每个索引之前使用的每个位的计数，然后我们可以在 O(1) 的复杂度内计算答案。
示例
#include<bits/stdc++.h>
using namespace std;
#define bits 32 // number of bits
int P[100000][bits+1];
bool Kset(int n, int k) {
if (n & (1 << (k - 1)))
return true;
return false;
}
void prefixArray(int n, int arr[]) { // building the prefix array
for (int i = 0; i <= bits; i++) {
P[0][i] = 0; // setting every bits initial count = 0
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= bits; j++) {
bool flag = Kset(arr[i], j);
if (i) // we add previous count to the latest count(0)
P[i][j] = P[i - 1][j];
if (flag) { // if jth bit is set so we increase the count
P[i][j]++;
}
}
}
}
int query(int L, int R, int K) {
if (L) // if L not equal to 0 then we return the prefix at R subtracted with prefix at L-1
return P[R][K] - P[L - 1][K];
else
return P[R][K];
}
int main() {
int arr[] = { 8, 9, 1, 3 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of given array
int queries[][3] = {
{ 1, 3, 4 },
{ 2, 4, 1 }
};
prefixArray(n, arr); // calling the function to create prefix array
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K) << "\n";
}
return 0;
}输出
2 3
由于我们正在维护前缀数组，这有助于我们在 O(1) 中找到答案，因此通过此操作，我们的时间复杂度大大降低到 O(N)，其中 N 是我们给定数组的大小。
上述代码的解释
在此程序中，我们为数组的每个索引维护一个前缀计数器，该计数器计算直到该索引为止使用的每个位。我们现在为我们的数组构建此计数，因为我们已经存储了每个位的数量前缀，所以对于第 k 位计数，我们需要用第 k 位到 R 索引的前缀计数减去第 k 位到 L-1 索引的前缀计数，这就是我们的答案。
结论
在本文中，我们解决了一个问题，即解决查询区间内第 K 位设置的数组元素数量。我们还学习了此问题的 C++ 程序以及解决此问题的完整方法（普通方法和高效方法）。我们可以在其他语言（如 C、Java、Python 和其他语言）中编写相同的程序。我们希望您发现本文有所帮助。
更新于：2021 年 11 月 26 日
248 次查看
广告