使用 C++ 查找按位 OR >= K 的子数组的数量

  • Z时代
  • 2024-01-10
  • 分类：综合

在本文中，我们将简要说明在 C++ 中解决按位 OR>=K 的子数组的数量。所以我们有一个数组 arr[] 和一个整数 K，我们必须找到OR(bitwise 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++ 解决问题 -

蛮力

在这种方法中，我们将简单地遍历所有可以形成的子数组并检查 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 和其他语言。希望这篇文章对您有所帮助。

以上是 使用 C++ 查找按位 OR >= K 的子数组的数量 的全部内容， 来源链接： utcz.com/z/317263.html

回到顶部