数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用C++查找按位或运算结果大于等于K的子数组个数
在本文中，我们将简要说明如何使用C++解决按位或运算结果大于等于K的子数组个数的问题。我们有一个数组arr[]和一个整数K，我们需要找到按位或(OR)运算结果大于等于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++解决这个问题：
暴力法
在这种方法中，我们将遍历所有可能的子数组，并检查其按位或运算结果是否大于等于K。如果是，则递增答案。
示例
#include <bits/stdc++.h>
using namespace std;
int main(){
int arr[] = {1, 2, 3}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(int); // the size of our array.
int answer = 0; // the counter variable.
for(int i = 0; i < size; i++){
int bitwise = 0; // the variable that we compare to k.
for(int j = i; j < size; j++){ // all the subarrays starting from 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运算符的一些特性，即即使我们添加更多数字，它也不会减小，因此，如果我们得到一个按位或运算结果大于等于K的子数组(从i到j)，则包含范围{i,j}的每个子数组的按位或运算结果都将大于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){ // segment tree building
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){ // for processing our queries or subarrays.
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}; // given array.
int k = 3;
int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
int answer = 0; // the counter variable.
build(arr, 1, 0, size - 1); // building segment tree.
for(int i = 0; i < size; i++){
int start = i, end = size-1;
int ind = INT_MAX;
while(start <= end){ // binary search
int mid = (start + end) / 2;
if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
ind = min(mid, ind);
end = mid - 1;
}
else
start = mid + 1;
}
if(ind != INT_MAX) // if ind is changed then increment the answer.
answer += size - ind;
}
cout << answer << "\n";
return 0;
}输出
4
在这种方法中，我们使用二分查找和线段树，这有助于将我们的时间复杂度从**O(N*N)降低到O(Nlog(N))**，这非常好。现在，与前面一种方法不同，此程序也可以处理更大的约束条件。
结论
在本文中，我们使用**二分查找和线段树**解决了查找按位或运算结果大于等于K的子数组个数的问题，时间复杂度为O(nlog(n))。我们还学习了针对此问题的C++程序以及解决此问题的完整方法（常规方法和高效方法）。我们可以使用C、Java、Python和其他语言编写相同的程序。希望本文对您有所帮助。
更新于：2021年11月24日
758 次浏览
广告