讲师中心 微信公众号

工具推荐

视频效率加速
updream

一键生成高质量推广成片

AniShort
AniShort

AI短剧协同制作平台

Laper
Laper

剧本策划到成片协作

Seko
Seko

AI短剧一键生成成片

使用C++编写代码,找到具有位或值大于或等于K的子数组的数量

秋明君_7879

秋明君_7879

发布时间:2023-08-27 15:17:06

|

1648人浏览过

|

来源于tutorialspoint

转载

使用c++编写代码,找到具有位或值大于或等于k的子数组的数量

在本文中,我们将简要说明如何在 C++ 中求解按位 OR>=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++ 来解决问题 -

暴力破解

在这种方法中,我们只是要遍历所有可以形成的子数组并检查 OR 是否大于或等于 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 是给定数组的大小,因此现在我们将采用一种有效的方法。

立即学习“C++免费学习笔记(深入)”;

高效方法

在这种方法中,我们将使用 OR 运算符的一些属性,即即使我们添加更多数字,它也不会减少,因此如果我们从 i 到 j 得到一个子数组,其 OR 大于或等于 K,那么每个包含范围 {i,j 的子数组} 将具有大于 K 的 OR,我们正在利用此属性并改进我们的代码。

示例

#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)),这非常好好的。现在,与前一个程序不同,该程序还可以适用于更大的约束。

结论

在本文中,我们解决了一个问题,以查找具有 OR >= K 的子数组的数量使用二分搜索和线段树,时间复杂度为 O(nlog(n))。我们还学习了解决这个问题的C++程序以及解决这个问题的完整方法(正常且高效)。我们可以用其他语言比如C、java、python等语言来编写同样的程序。希望这篇文章对您有所帮助。

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

c++怎么学习?c++怎么入门?c++在哪学?c++怎么学才快?不用担心,这里为大家提供了c++速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
Laper
Laper Hot

Laper是专为编剧、导演和制片人推出的 AI 原生剧本创作工具。

Atoms
Atoms Hot

Atoms是一款AI智能体工具,第一支自动构建真实业务的 AI 团队。

UpDream
UpDream Hot

一款AI视频创作工具,主要用于哔哩哔哩推出的自研AI视频创作工具,适合需要提升相关任务效率的用户。

Loomy
Loomy Hot

一款AI工具,主要用于科大讯飞发布的桌面级 AI 助理,比 OpenClaw 更易用、更安全!,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

超级麦吉

一款通过数字员工协作完成调研、数据分析与文档制作的AI办公平台。

小橡皮AI

一款AI工具,主要用于小橡皮一键去AI味,将机器味重的内容改得更有活人感,防止因为 AI 内容被平台打上 AI 标签,以及限流,适合需要提升相关任务效率的用户。

相关专题

更多
java基础知识汇总
java基础知识汇总

java基础知识有Java的历史和特点、Java的开发环境、Java的基本数据类型、变量和常量、运算符和表达式、控制语句、数组和字符串等等知识点。想要知道更多关于java基础知识的朋友,请阅读本专题下面的的有关文章,欢迎大家来php中文网学习。

6424

2023.10.24

Go语言中的运算符有哪些
Go语言中的运算符有哪些

Go语言中的运算符有:1、加法运算符;2、减法运算符;3、乘法运算符;4、除法运算符;5、取余运算符;6、比较运算符;7、位运算符;8、按位与运算符;9、按位或运算符;10、按位异或运算符等等。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

3584

2024.02.23

php三元运算符用法
php三元运算符用法

本专题整合了php三元运算符相关教程,阅读专题下面的文章了解更多详细内容。

1952

2025.10.17

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

140

2026.11.12

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

100

2026.11.12

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

60

2026.11.12

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

160

2026.11.06

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

140

2026.11.06

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

120

2026.11.06

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
C++ Reference
C++ Reference

共0课时 | 0人学习

RabbitMQ 教程手册
RabbitMQ 教程手册

共0课时 | 0人学习

C# 教程
C# 教程

共94课时 | 22.9万人学习

关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn