789. 数的范围

蔚落 2024-05-01 16:07 63阅读 0赞

> 给定一个按照升序排列的长度为 nn 的整数数组，以及 qq 个查询。
> 
> 对于每个查询，返回一个元素 kk 的起始位置和终止位置（位置从 00 开始计数）。
> 
> 如果数组中不存在该元素，则返回 `-1 -1`。

输入格式

> 第一行包含整数 nn 和 qq，表示数组长度和询问个数。
> 
> 第二行包含 nn 个整数（均在 1∼100001∼10000 范围内），表示完整数组。
> 
> 接下来 qq 行，每行包含一个整数 kk，表示一个询问元素。

输出格式

> 共 q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
> 
> 如果数组中不存在该元素，则返回 `-1 -1`。

数据范围

> 1≤n≤1000001≤n≤100000  
> 1≤q≤100001≤q≤10000  
> 1≤k≤100001≤k≤10000

输入样例：

6 3
    1 2 2 3 3 4
    3
    4
    5

输出样例：

3 4
    5 5
    -1 -1

#include<iostream>
    #include<algorithm>
    using namespace std;
     
    const int N=100010;
    int n,m;
    int q[N];
    
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=0;i<=n-1;++i)scanf("%d",&q[i]);
    	while (m--)
    	{
    		int x;scanf("%d",&x);
    		int l=0,r=n-1;
    		while(l<r){
    			int mid=l+r>>1;
    			if(q[mid]>=x)r=mid;
    			else l=mid+1;
    		}
    		if(q[l]!=x)cout<<"-1 -1"<<endl;
    		else{
    			cout <<l<<' ';
    			int l=0,r=n-1;
    			while(l<r)
    			{
    				int mid=l+r+1>>1;
    				if(q[mid]<=x) l=mid;
    				else r=mid-1;
    			}
    			cout<<l<<endl;
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，63人围观）

还没有评论，来说两句吧...

相关阅读

相关 789. 数的范围

给定一个按照升序排列的长度为nn的整数数组，以及qq个查询。对于每个查询，返回一个元素kk的起始位置和终止位置（位置从00开始计数）。如果数组中不存在该元素，则返回-1 ...

蔚落/ 2024年05月01日 16:07/ 0 赞/ 64 阅读

相关数的范围(考查二分)

数的范围(考查二分) 给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

今天药忘吃喽~/ 2024年03月31日 14:05/ 0 赞/ 44 阅读

相关二分 AcWing 789. 数的范围

二分 AcWing 789. 数的范围原题链接 [AcWing 789. 数的范围][AcWing 789.] 算法标签二分思路采用二分，

短命女/ 2023年09月28日 11:10/ 0 赞/ 20 阅读

相关求指定范围内的最大数

同学们都知道，无论哪个语言入门学习时，第一个Sample都是“Hello world！”，我们学习算法，第一个入门的问题也许就是求给定输入的最大或者最小，那么我们今天也来求解这

绝地灬酷狼/ 2023年02月23日 05:25/ 0 赞/ 40 阅读

相关 vue 实现两个数的取值范围

文章目录 1：实现的效果 2：实现步骤 > 讲解：此功能分为左输入框和右输入框 > 限制条件： > 1：只能输入数字 > 2：左边的数值不能大于

àì夳堔傛蜴生んèń/ 2022年12月27日 12:51/ 0 赞/ 199 阅读

相关 789_AUTOSAR_RS_SystemTemplate4_通信3

全部学习汇总： [https://github.com/GreyZhang/hack\_autosar][https_github.com_GreyZhang_h

拼搏现实的明天。/ 2022年09月11日 10:23/ 0 赞/ 104 阅读

相关 789. 逃脱阻碍者

2021-08-22 LeetCode每日一题链接：[https://leetcode-cn.com/problems/escape-the-ghosts/][http

た入场券/ 2022年09月07日 09:31/ 0 赞/ 126 阅读

相关 leetcode789逃脱阻碍者

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

àì夳堔傛蜴生んèń/ 2022年09月07日 09:28/ 0 赞/ 101 阅读

相关 8位有符号数的补码表示范围

范围是 -128至127. 根据补码的几条规定即可推出上述结论： 1 若二进制每位全为0,则表示数0 2 若最高位（即符号位）为0,表示正数

不念不忘少年蓝@/ 2022年06月12日 04:47/ 0 赞/ 225 阅读

相关 python-指定范围内的互满数

def fullnum(x,y): int(x) int(y) List_1=[] List_2=[]

冷不防/ 2022年06月02日 10:05/ 0 赞/ 227 阅读