8. 查找
1 题目描述
查找
| 成绩 | 10 | 开启时间 | 2021年09月24日 星期五 18:00 |
| 折扣 | 0.8 | 折扣时间 | 2021年11月15日 星期一 00:00 |
| 允许迟交 | 否 | 关闭时间 | 2021年11月23日 星期二 00:00 |
输入 n(n ≤ 10^6)个不超过 10^9的单调不减的(就是后面的数字不小于前面的数字)非负整数 ,然后进行 m(m ≤ 10^5) 次询问。
对于每次询问,给出一个整数 q(q ≤ 10^9),要求输出这个数字在序列中第一次出现的编号,如果没有找到的话输出 -1 。
输入描述
第一行 2 个整数 n 和 m,表示数字个数和询问次数。
第二行 n 个整数,表示这些待查询的数字,有序
第三行 m 个整数,表示询问这些数字的编号,从 1 开始编号。
输出描述
m 个整数表示答案,注意换行。
接下来将由系统输出你的询问记录。
当你的答案正确且你询问的次数在( 2 * m * log(n) ) + 3次以内时,你将AC此题。此题log以2为底。
PS:部分超过时间限制的可多次提交,即可通过
预设代码
前置代码
/* PRESET CODE BEGIN - NEVER TOUCH CODE BELOW */ #include <bits/stdc++.h> int n, m, q, a[1000005]; int find(int x,int n);
int cmp(int i, int x)
{ if(i > n|| i <= 0) return -2; if (a[i] > x) return 1; if (a[i] == x) return 0; return -1;
} int main()
{ scanf("%d %d", &n, &m); //读入 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //还是读入 for (int i = 1; i <= m; i++) { scanf("%d", &q); int ans = find(q,n); //看看查找的结果 printf("%d ", ans); //输出 } printf("\n"); return 0;
} // //请补充下列代码
// int find(int x,int n)
// { // } /* PRESET CODE END - NEVER TOUCH CODE ABOVE */
| 测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
|---|---|---|---|---|---|
| 测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 153600KB | 0 |
2 代码
#include <bits/stdc++.h> int n, m, q, a[1000005]; int find(int x,int n);
int cmp(int i, int x)
{ if(i > n|| i <= 0) return -2; if (a[i] > x) return 1; if (a[i] == x) return 0; return -1;
} int main()
{ freopen("file in.txt","r",stdin);scanf("%d %d", &n, &m); //读入 for (int i = 1; i <= n; i++) scanf("%d", &a[i]); //还是读入 for (int i = 1; i <= m; i++) { scanf("%d", &q); int ans = find(q,n); //看看查找的结果 printf("%d ", ans); //输出 } printf("\n"); return 0;
} // //请补充下列代码
//找x在a中第一次出现的编号
// int find(int x,int n)
// {
// int mid;
// int ans;
// int left,right;
// int flag=0;// left=1;right=n;
// mid=0;// //数字个数大于等于3个才会进入这个循环
// while(left<right-1){// /*if((right-left+1)%2==1){
// // 奇数
// mid = (right-left)/2+left;
// }
// else{
// mid = (right-left)/2+left;
// }*/
// //不用考虑奇偶性
// mid = (right-left)/2+left;
// // 比较中间这个数和x的大小
// ans = cmp(mid,x);
// if(ans==-2){
// exit;
// }
// else if(ans==1){
// // 这个数在左边
// right = mid;
// }
// else if(ans==-1){
// //这个数在右边
// left=mid;
// }
// else{
// // 找到了
// flag=1;
// break;
// }
// }
// //如果上面的循环没有找到,那么还剩下三个数没有找 left left+1 right
// // 或者说直接没有进入上面的while循环中
// if(flag==0){
// while(left<=right){
// ans = cmp(left,x);
// if(ans==0){
// //找到的话直接返回left的值并且退出这个函数了
// return left;
// }
// else{
// left++; // }
// }
// //如果循环走完了都没有退出这个函数,说明没有找到相等的数
// return -1;
// }// //如果是在while循环里面找到的就会运行下面的语句
// if(flag){
// //找到了这个数,但是还要验证他是不是第一次出现
// while(mid-1>=1){
// ans=cmp(mid-1,x);
// if(ans==0){
// //他的前一个数还是和他相等
// mid--;
// }
// else{
// //他的前一个数和x不相等,那么现在这个mid就是我们要找的第一次出现的x
// break;
// }
// }
// return mid;
// }
// else
// return -1;
// }// 再循环里面找到这个数的时候不要退出,继续循环二分法
// 如果前面有的话,最终会落在这个数上面,如果没有的话,最后left也会回到这个数,和right相等
int find(int x, int n){int left,right;int mid;int ans;int flag=0,temp;left=1;right=n;while(left<=right){// 没有必要区分奇偶,这里只需要让mid取中就行,并不是前面那种两个两个拿出来会有一个落单的情况mid=(right-left)/2+left;ans= cmp(mid,x);if(ans==-2){exit(0);}else if(ans==1){// mid这个数已经比较过了,不用在比较了,直接向前面推进一个数right = mid-1;}else if(ans==-1){left=mid+1;}else{right = mid-1;//不往前推的话这个就会进入死循环temp=mid;//把这个数记录下来,防止往前推以后没有这个数了flag=1;}}// 循环结束之后if(ans==0)return left;else if(flag==1)return temp;return -1;
}// 不用区分n的奇偶性
// mid比较过后应该跳过,简化了算法的复杂度
相关文章:
8. 查找
1 题目描述 查找成绩10开启时间2021年09月24日 星期五 18:00折扣0.8折扣时间2021年11月15日 星期一 00:00允许迟交否关闭时间2021年11月23日 星期二 00:00 输入 n(n ≤ 10^6)个不超过 10^9的单调不减的(就是后面的数字不小于前面的数字)非负整数 &#…...
二分查找算法
感谢“五点七边”工作室的算法讲解,详细内容可以参考视频讲解 二分查找为什么总是写错?_哔哩哔哩_bilibili 此处仅是个人学习总结 以target等于5为例,输入: 1 2 3 5 5 5 8 9 1. 找到第一个 > target 的元素 判断条件 < target&am…...
Git(3)之远程服务器
Git基础之远程服务器 Author:onceday date:2023年3月5日 满满长路有人对你微笑过嘛… windows安装可参考文章:git简易配置_onceday_CSDN博客 參考文档: 《progit2.pdf》,Progit2 Github。《git-book.pdf》 文章目…...
Javalin解构
Javalin Javalin是一个轻量级http框架,我们可以很容易的了解请求的处理过程及其设计,具有较高的学习意义。 从demo说起 public static void main(String[] args) {Javalin app Javalin.create(config -> {System.out.println("用户配置"…...
yolov5算法,训练模型,模型检测
嘟嘟嘟嘟!工作需要,所以学习了下yolov5算法。是干什么的呢? 通俗来说,可以将它看做是一个小孩儿,通过成年人(开发人员)提供的大量图片的学习,让自己知道我看到的哪些场景需要提醒给成…...
linux系统防火墙开放端口
linux系统防火墙开放端口 在外部访问CentOS中部署应用时,需要通过防火墙管理软件,开端口,或者直接关闭防火墙进行解决(不建议) 加粗样式 常用命令: systemctl start firewalld #启动 systemctl stop firewalld #停止 systemctl status firewalld #查看…...
CSAPP第九章 虚拟内存
理解虚拟内存的原因 本章前部分描述虚拟内存是如何工作的,后一部分描述应用程序如何使用和管理虚拟内存 物理和虚拟寻址 虚拟内存作为缓存的工具 页表 页命中 缺页 虚拟内存作为内存管理的工具 简化链接,简化加载,简化共享,简化…...
numpy数组与矩阵运算(二)
文章目录矩阵生成与常用操作矩阵生成矩阵转置查看矩阵特性矩阵乘法计算相关系数矩阵计算方差、协方差、标准差计算特征值与特征向量计算逆矩阵求解线性方程组奇异值分解函数向量化矩阵生成与常用操作 矩阵生成 扩展库numpy中提供的matrix()函数可以用来把列表、元组、range对…...
Dubbo 中 Zookeeper 注册中心原理分析
Dubbo 中 Zookeeper 注册中心原理分析 文章目录Dubbo 中 Zookeeper 注册中心原理分析一、ZooKeeper注册中心1.1 ZooKeeper数据结构1.2 ZooKeeper的Watcher机制1.3 ZooKeeper会话机制1.4 使用ZooKeeper作为注册中心二、源码分析2.1 AbstractRegistry2.2 FailbackRegistry2.2.1 核…...
素数产生新的算法(由筛法减法改为增加法)--哥德巴赫猜想的第一次实际应用
素数产生新的算法(由筛法减法改为增加法)--哥德巴赫猜想的第一次实际应用 摘要:长期以来,人们认为哥德巴赫猜想没有什么实际应用的。 现在,我假设这个不是猜想,而是定理或公理,就产生了新的应用…...
递归-需要满足三个条件
一,概述 递归是一种应用非常广泛的算法(或者编程技巧)。很多数据结构和算法的编码实现都要用到递归,比如 DFS 深度优先搜索、前中后序二叉树遍历等。 去的过程叫“递”,回来的过程叫“归”。基本上所有的递归问题都可…...
【剑指Offer-Java】两个栈实现队列
题目 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 输入: [“CQueue”,“appendT…...
Allegro如何将Waived掉的DRC显示或隐藏操作指导
Allegro如何将Waived掉的DRC显示或隐藏操作指导 在用Allegro做PCB设计的时候,如果遇到正常的DRC,可以用Waive的命令将DRC不显示,如下图 当DRC被Waive掉的时候,如何将DRC再次显示出来。类似下图效果 具体操作如下 点击Display...
MATLAB——数据及其运算
MATLAB数值数据数值数据类型的分类1.整型整型数据是不带小数的数,有带符号整数和无符号整数之分。表中列出了各种整型数据的取值范围和对应的转换函数。2.浮点型浮点型数据有单精度(single)和双精度((double)之分&…...
【微信小程序】-- 页面导航 -- 声明式导航(二十二)
💌 所属专栏:【微信小程序开发教程】 😀 作 者:我是夜阑的狗🐶 🚀 个人简介:一个正在努力学技术的CV工程师,专注基础和实战分享 ,欢迎咨询! &…...
gdb查看汇编代码的例子
gdb查看汇编代码的例子 操作步骤 用 gdb 启动可执行文件:gdb executable_file在 gdb 中设置断点:break function_name 或者 break *memory_address运行程序:run当程序停止在断点处时,使用 disassemble 命令来查看汇编代码&#…...
第四讲:如何将本地代码与服务器代码保持实时同步
一、前言 在我们进行 Ambari 二次开发时,通常会先在服务器上部署一套可以使用的 Ambari 环境。 二次开发,就肯定是要改动代码的,我们不能老是在服务器上用vim编辑文件,那样效率太低,始终不是长久之计。 所以我们需要在本地打开我们的Ambari源码项目,比如用idea工具,可…...
cuda调试(一)vs2019-windows-Nsight system--nvtx使用,添加nvToolsExt.h文件
cuda调试 由于在编程过程中发现不同的网格块的结构,对最后的代码结果有影响,所以想记录一下解决办法。 CUDA的Context、Stream、Warp、SM、SP、Kernel、Block、Grid cuda context (上下文) context类似于CPU进程上下,表示由管理层 Drive …...
向Spring容器中注入bean有哪几种方式?
文章前言: 写这篇文章的时候,我正在手机上看腾讯课堂的公开课,有讲到 Spring IOC 创建bean有哪几种方式,视频中有提到过 set注入、构造器注入、注解方式注入等等;于是,就想到了写一篇《Spring注入bean有几种…...
如何用 Python采集 <豆某yin片>并作词云图分析 ?
嗨害大家好鸭!我是小熊猫~ 总有那么一句银幕台词能打动人心 总有那么一幕名导名作念念不忘 不知道大家有多久没有放松一下了呢? 本次就来给大家采集一下某瓣电影并做词云分析 康康哪一部才是大家心中的经典呢? 最近又有哪一部可能会成为…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
