在本文中，我们将讨论一个问题，即找到给定范围内具有第k位设置的元素的数量，例如 −
Input : arr[] = { 4, 5, 7, 2 }Query 1: L = 2, R = 4, K = 4Query 2: L = 3, R = 5, K = 1Output : 0 1
我们将通过一种蛮力的方法来解决这个问题，并看看这种方法是否适用于更高的约束条件。如果不适用，那么我们尝试思考一种新的高效方法。
蛮力方法
在这种方法中，我们只需遍历范围并检查每个元素的第k位是否设置，如果是，则增加计数。
示例
#includeusing namespace std;#define MAX_BITS 32bool 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;}
输出
01
上述方法的时间复杂度为O(N*Q)，其中N是数组的大小，Q是给定的查询数量；如您所见，这种方法对于更高的约束条件不适用，因为它将花费太多时间，所以现在我们将尝试制作一个高效的程序。
立即学习“C++免费学习笔记（深入）”；
高效的方法
在这种方法中，我们将维护一个二维前缀和数组，该数组将保持每个索引位置使用的位数，并且我们可以在O(1)的复杂度中计算出答案。
示例
#includeusing namespace std;#define bits 32 // number of bitsint 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;}
输出
23
由于我们正在维护帮助我们以O(1)的时间复杂度找到答案的前缀数组，所以我们的时间复杂度大大降低到了O(N)，其中N是给定数组的大小。
上述代码的解释
在这个程序中，我们为数组的每个索引维护一个前缀计数器，用于计算该索引之前使用的每个位数。现在，我们已经存储了每个位数的前缀计数，所以对于第k位的计数，我们需要用第R索引处的第k位的前缀计数减去第L-1索引处的第k位的前缀计数，这就是我们的答案。
结论
在本文中，我们解决了一个问题，即解决具有第K位设置的范围内数组元素的查询。我们还学习了这个问题的C++程序以及我们解决这个问题的完整方法（普通和高效）。我们可以用其他语言（如C、Java、Python和其他语言）编写相同的程序。希望您会觉得这篇文章有帮助。
以上就是使用C++编写的查询在范围内具有第K位设置的数组元素数量的代码的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444232.html
微信扫一扫 
支付宝扫一扫 
