789. 数的范围
范围
2023-09-14 09:14:58 时间
Question
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。
第二行包含 n 个整数(均在 1∼10000 范围内),表示完整数组。
接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
Ideas
整数二分
Code
n,m = list(map(int,input().strip().split()))
lis = list(map(int,input().strip().split()))
for i in range(m):
x = int(input())
l,r = 0,n-1
while l < r:
mid = l + r >> 1
if lis[mid] >= x:
r = mid
else:
l = mid + 1
# 二分一定有答案,但是答案不一定符合题目要求
if lis[l] != x:
print(-1,-1)
else:
print(l,end=' ')
r = n-1
while l < r:
mid = l + r + 1 >> 1
if lis[mid] <= x:
l = mid
else:
r = mid - 1
print(r)
相关文章
- ASP.NET中 RangeValidator(范围验证)的使用[通俗易懂]
- 【说站】Java中copyOfRange()的范围拷贝
- php案例:判断IP地址是否合法+IP地址范围区间
- JS正则表达式从入门到入土(3)—— 范围类详解编程语言
- 精准掌握Redis时间范围(redis时间范围)
- Linux主机IP地址范围确定方法(linux主机地址范围)
- Oracle数据库中的范围分区机制(Oracle中 范围分区)
- 为什么MySQL不在关键字范围内(mysql 不在范围内)
- MySQL数据筛选如何排除指定范围的数据(mysql不在某范围内)
- MySQL实现不在某个范围内的查询当字段不在给定值列表中时,使用NOT IN语法(mysql 不in)
- Oracle会话范围一种更高效的管理方式(oracle会话范围)
- Oracle中整型数据类型的取值范围(oracle中整型的范围)
- 共享锁using范围的实现方法
- JSP动态生成验证码存储在session作用范围内