使用 C++ 查找按位 OR >= K 的子数组的数量
在本文中,我们将简要说明在C++中解决按位OR>=K的子数组的数量。所以我们有一个数组arr[]和一个整数K,我们必须找到OR(bitwiseor)大于或等于K的子数组的数量。所以这里是给定问题的例子-
Input: arr[] = {1, 2, 3} K = 3 Output: 4 Bitwise OR of sub-arrays: {1} = 1 {1, 2} = 3 {1, 2, 3} = 3 {2} = 2 {2, 3} = 3 {3} = 3 4 sub-arrays have bitwise OR ≥ 3 Input: arr[] = {3, 4, 5} K = 6 Output: 2
寻找解决方案的方法
现在我们将使用两种不同的方法来使用C++解决问题-
蛮力
在这种方法中,我们将简单地遍历所有可以形成的子数组并检查OR是否大于或等于K。如果是,那么我们将增加我们的答案。
示例
#include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1, 2, 3}; //给定数组。 int k = 3; int size = sizeof(arr) / sizeof(int); //我们数组的大小。 int answer = 0; //计数器变量。 for(int i = 0; i < size; i++){ int bitwise = 0; //我们与k比较的变量。 for(int j = i; j < size; j++){ //从i开始的所有子数组。 bitwise = bitwise | arr[j]; if(bitwise >= k) // if bitwise >= k increment answer. answer++; } } cout << answer << "\n"; return 0; }输出结果
4
这种方法非常简单,但它有它的缺陷,因为这种方法对于更高的约束不是很好,因为这种方法的时间复杂度是O(N*N),其中N是给定数组的大小,所以现在我们要寻找一种有效的方法。
有效的方法
在这种方法中,我们将使用OR运算符的一些属性,即即使我们添加更多数字它也不会减少,因此如果我们从i到j得到一个OR大于或等于K的子数组,那么每个包含范围{i,j}的子数组的OR大于K,我们正在利用此属性并改进我们的代码。
示例
#include <bits/stdc++.h> #define N 1000 using namespace std; int t[4*N]; void build(int* a, int v, int start, int end){ //分段树构建 if(start == end){ t[v] = a[start]; return; } int mid = (start + end)/2; build(a, 2 * v, start, mid); build(a, 2 * v + 1, mid + 1, end); t[v] = t[2 * v] | t[2 * v + 1]; } int query(int v, int tl, int tr, int l, int r){ //用于处理我们的查询或子数组。 if (l > r) return 0; if(tl == l && tr == r) return t[v]; int tm = (tl + tr)/2; int q1 = query(2*v, tl, tm, l, min(tm, r)); int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r); return q1 | q2; } int main(){ int arr[] = {1, 2, 3}; //给定数组。 int k = 3; int size = sizeof(arr) / sizeof(arr[0]); //我们数组的大小。 int answer = 0; //计数器变量。 build(arr, 1, 0, size - 1); //构建段树。 for(int i = 0; i < size; i++){ int start = i, end = size-1; int ind = INT_MAX; while(start <= end){ //二分查找 int mid = (start + end) / 2; if(query(1, 0, size-1, i, mid) >= k){ //检查子数组。 ind = min(mid, ind); end = mid - 1; } else start = mid + 1; } if(ind != INT_MAX) //如果ind改变,则增加答案。 answer += size - ind; } cout << answer << "\n"; return 0; }输出结果
4
在这种方法中,我们使用二分搜索和段树,这有助于将时间复杂度从O(N*N)降低到O(Nlog(N)),这是非常好的。现在,与前一个程序不同,该程序还可以用于更大的约束。
结论
在本文中,我们nlog(n)使用二叉搜索和分段树解决了一个问题,即在O()时间复杂度中找到OR>=K的子数组的数量。我们还学习了针对这个问题的C++程序以及我们解决这个问题的完整方法(普通和高效)。我们可以用其他语言编写相同的程序,例如C、java、python和其他语言。希望这篇文章对您有所帮助。