二分排序

二分问题之前遇到很多次了,不过一直是手写完整二分,现在转变一下想法,直接使用函数lower_bound和upper_bound更方便

lower_bound

 有序数组中 查找第一个不小于指定值的位置。

本质二分代码:

int lower_bound_custom(int* arr, int n, int val) {int low = 0, high = n; // 查找范围 [low, high)while (low < high) {int mid = low + (high - low) / 2;if (arr[mid] < val) {low = mid + 1; // 继续查找右区间} else {high = mid; // 继续查找左区间}}return low; // 返回第一个不小于 val 的位置
}

upper_bound 

 有序数组中 查找第一个大于指定值的位置

本质二分代码:

int upper_bound_custom(int* arr, int n, int val) {int low = 0, high = n; // 查找范围 [low, high)while (low < high) {int mid = low + (high - low) / 2;if (arr[mid] <= val) {low = mid + 1; // 继续查找右区间} else {high = mid; // 继续查找左区间}}return low; // 返回第一个大于 val 的位置
}

注意 lower_bound和upper_bound 是指针用法,最后返回的是位置索引

真题实战

题目链接:1.递增三元组 - 蓝桥云课

利用 lower_bound和upper_bound 减少时间复杂度

代码一:

纯暴力思想,发现有2个测试样例无法通过,时间超时,此时时间复杂度为O(n^3)

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],b[100010],c[100010];
long long sum=0;
int main()
{cin>>n;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=n; i++) cin>>b[i];for(int i=1; i<=n; i++) cin>>c[i];for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){for(int k=1; k<=n; k++){if(a[i]<b[j] && b[j]<c[k]){sum++;    }}}}cout<<sum<<endl;return 0;
}

代码二:

优化遍历,发现只需要两重for循环,找到每个b[i]位置符合的a[]个数和c[]个数,累成再累加,但是还是有一个样例无法通过,此时时间复杂度为O(n^2)

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],b[100010],c[100010];
long long sum=0;
int main()
{cin>>n;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=n; i++) cin>>b[i];for(int i=1; i<=n; i++) cin>>c[i];for(int i=1;i<=n;i++){int sum_a=0,sum_c=0;for(int j=1;j<=n;j++){if(a[j]<b[i]){sum_a++;}if(b[i]<c[j]){sum_c++;}}sum+=1LL*sum_a*sum_c;}cout<<sum<<endl;return 0;
}

代码三:

最后想到通过二分排序,减少时间复杂度,通过所有测试样例,此时时间复杂度为O(n^logn)

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100010],b[100010],c[100010];
long long sum=0;
int main()
{cin>>n;for(int i=1; i<=n; i++) cin>>a[i];for(int i=1; i<=n; i++) cin>>b[i];for(int i=1; i<=n; i++) cin>>c[i];sort(a+1,a+n+1);sort(b+1,b+n+1);sort(c+1,c+n+1);for(int j=1;j<=n;j++){int sum_a=lower_bound(a+1,a+n+1,b[j])-(a+1); //满足 a[i] < b[j]int sum_c=(c+n+1)-upper_bound(c+1,c+n+1,b[j]); //满足 b[j] < c[k]sum+=1LL*sum_a*sum_c; //可能超int型范围 }cout<<sum<<endl;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/477238.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

探索 RocketMQ:企业级消息中间件的选择与应用

一、关于RocketMQ RocketMQ 是一个高性能、高可靠、可扩展的分布式消息中间件&#xff0c;它是由阿里巴巴开发并贡献给 Apache 软件基金会的一个开源项目。RocketMQ 主要用于处理大规模、高吞吐量、低延迟的消息传递&#xff0c;它是一个轻量级的、功能强大的消息队列系统&…

李宏毅机器学习课程知识点摘要(6-13集)

pytorch简单的语法和结构 dataset就是数据集&#xff0c;dataloader就是分装好一堆一堆的 他们都是torch.utils.data里面常用的函数&#xff0c;已经封装好了 下面的步骤是把数据集读进来 这里是读进来之后&#xff0c;进行处理 声音信号&#xff0c;黑白照片&#xff0c;红…

Wekan看板安装部署与使用介绍

Wekan看板安装部署与使用介绍 1. Wekan简介 ​ Wekan 是一个开源的看板式项目管理工具&#xff0c;它的配置相对简单&#xff0c;因为大多数功能都是开箱即用的。它允许用户以卡片的形式组织和跟踪任务&#xff0c;非常适合敏捷开发和日常任务管理。Wekan 的核心功能包括看板…

【Mysql】开窗聚合函数----SUM,AVG, MIN,MAX

1、概念 在窗口中&#xff0c;每条记录动态地应用聚合函数&#xff08;如&#xff1a;SUM(),AVG(),MAX(),MIN(),COUNT(),&#xff09;可以动态计算在指定的窗口内的各种聚合函数值。 2、操作 以下操作将基于employee表进行操作。 sum() 进行sum的时候&#xff0c;没有order …

EWA Volume Splatting

摘要 本文提出了一种基于椭圆高斯核的直接体绘制新框架&#xff0c;使用了一种投影方法&#xff08;splatting approach&#xff09;。为避免混叠伪影&#xff08;aliasing artifacts&#xff09;&#xff0c;我们引入了一种重采样滤波器的概念&#xff0c;该滤波器结合了重建核…

Vue实训---0-完成Vue开发环境的搭建

1.在官网下载和安装VS Code编辑器 完成中文语言扩展&#xff08;chinese&#xff09;&#xff0c;安装成功后&#xff0c;需要重新启动VS Code编辑器&#xff0c;中文语言扩展才可以生效。 安装Vue-Official扩展&#xff0c;步骤与安装中文语言扩展相同&#xff08;专门用于为“…

C# 超链接控件LinkLabel无法触发Alt快捷键

在C#中&#xff0c;为控件添加快捷键的方式有两种&#xff0c;其中一种就是Windows中较为常见的Alt快捷键&#xff0c;比如运行对话框&#xff0c;记事本菜单等。只需要按下 Alt 框号中带下划线的字母即可触发该控件的点击操作。如图所示 在C#开发中&#xff0c;实现类似的操作…

赛氪媒体支持“2024科普中国青年之星创作交流活动”医学专场落幕

2024年11月15日下午&#xff0c;由中国科普作家协会、科普中国发展服务中心主办&#xff0c;什刹海文化展示中心承办&#xff0c;并携手国内产学研一体融合领域的领军者——赛氪网共同支持的“2024科普中国青年之星创作交流活动”医学科普专场&#xff0c;在什刹海文化展示中心…

《现代制造技术与装备》是什么级别的期刊?是正规期刊吗?能评职称吗?

​问题解答 问&#xff1a;《现代制造技术与装备》是不是核心期刊&#xff1f; 答&#xff1a;不是&#xff0c;是知网收录的第二批认定学术期刊。 问&#xff1a;《现代制造技术与装备》级别&#xff1f; 答&#xff1a;省级。主管单位&#xff1a;齐鲁工业大学&#xff0…

(十一)Python字符串常用操作

一、访问字符串值 Python访问子字符串变量&#xff0c;可以使用方括号来截取字符串。与列表的索引一样&#xff0c;字符串索引从0开始。 hh"LaoTie 666" hh[2] mm"床前明月光" mm[3] 字符串的索引值可以为负值。若索引值为负数&#xff0c;则表示由字符…

数据结构(初阶6)---二叉树(遍历——递归的艺术)(详解)

二叉树的遍历与练习 一.二叉树的基本遍历形式1.前序遍历(深度优先遍历)2.中序遍历(深度优先遍历)3.后序遍历(深度优先遍历)4.层序遍历&#xff01;&#xff01;(广度优先遍历) 二.二叉树的leetcode小练习1.判断平衡二叉树1&#xff09;正常解法2&#xff09;优化解法 2.对称二叉…

20.100ASK_T113-PRO 开发板开机自动QT程序简单的方法一

本文详细介绍了在嵌入式系统中实现程序开机自启动的多种方法&#xff0c;包括通过修改/etc/profile、/etc/rc.local文件&#xff0c;以及在/etc/init.d目录下创建启动脚本等方式。文章还解释了不同配置文件的作用及它们之间的区别。 开机自动启动QT应用程序 用户模式下的启动 …

Android蓝牙架构,源文件目录/编译方式学习

Android 版本 发布时间 代号&#xff08;Codename&#xff09; Android 1.0 2008年9月23日 无 Android 1.1 2009年2月9日 Petit Four Android 1.5 2009年4月27日 Cupcake Android 1.6 2009年9月15日 Donut Android 2.0 2009年10月26日 Eclair Android 2.1 2…

LeetCode 145.二叉树的后序遍历

题目&#xff1a;给你一棵二叉树的根节点 root &#xff0c;返回其节点值的 后序遍历 。 思路&#xff1a;左 右 根 代码&#xff1a; /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* Tre…

GitLab|数据迁移

注意&#xff1a;新服务器GitLab版本需和旧版本一致 在旧服务器执行命令进行数据备份 gitlab-rake gitlab:backup:create 备份数据存储在 /var/opt/gitlab/backups/ 将备份数据传输到新服务器的/var/opt/gitlab/backups/下&#xff0c;并修改文件权限&#xff08;下载前和上传…

实验四:构建园区网(OSPF 动态路由)

目录 一、实验简介 二、实验目的 三、实验需求 四、实验拓扑 五、实验步骤 1、在 eNSP 中部署网络 2、设计全网 IP 地址 3、配置二层交换机 4、配置路由交换机并测试通信 5、配置路由接口地址 6、配置 OSPF 动态路由&#xff0c;实现全网互通 一、实验简介 使用路由…

外卖系统开发实战:从架构设计到代码实现

开发一套外卖系统&#xff0c;需要在架构设计、技术选型以及核心功能开发等方面下功夫。这篇文章将通过代码实例&#xff0c;展示如何构建一个基础的外卖系统&#xff0c;从需求梳理到核心模块的实现&#xff0c;帮助你快速掌握开发要点。 一、系统架构设计 一个完整的外卖系…

“AI玩手机”原理揭秘:大模型驱动的移动端GUI智能体

作者&#xff5c;郭源 前言 在后LLM时代&#xff0c;随着大语言模型和多模态大模型技术的日益成熟&#xff0c;AI技术的实际应用及其社会价值愈发受到重视。AI智能体&#xff08;AI Agent&#xff09;技术通过集成行为规划、记忆存储、工具调用等机制&#xff0c;为大模型装上…

C语言——break、continue、goto

目录 一、break 二、continue 1、在while循环中 2、在for循环中 三、go to 一、break 作用是终止循环&#xff0c;在循环内遇到break直接就跳出循环。 注&#xff1a; 一个break语句只能跳出一层循环。 代码演示&#xff1a; #include<stdio.h>void test01() {for (…

AR智能眼镜|AR眼镜定制开发|工业AR眼镜方案

AR眼镜的设计与制造成本主要受到芯片、显示屏和光学方案的影响&#xff0c;因此选择合适的芯片至关重要。一款优秀的芯片平台能够有效提升设备性能&#xff0c;并解决多种技术挑战。例如&#xff0c;采用联发科八核2.0GHz处理器&#xff0c;结合12nm制程工艺&#xff0c;这种低…