数的范围(整数二分)
2020-01-12 16:03:29来源:博客园 阅读 ()
数的范围(整数二分)
给定一个按照升序排列的长度为n的整数数组,以及 q 个查询。
对于每个查询,返回一个元素k的起始位置和终止位置(位置从0开始计数)。
如果数组中不存在该元素,则返回“-1 -1”。
输入格式
第一行包含整数n和q,表示数组长度和询问个数。
第二行包含n个整数(均在1~10000范围内),表示完整数组。
接下来q行,每行包含一个整数k,表示一个询问元素。
输出格式
共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
可以直接顺序查找,但时间O(n);而二分查找时间O(logn)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int q=scan.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++) a[i]=scan.nextInt(); while(q-->0){ int num=scan.nextInt(); //先找到左边界 int l=0,r=n-1; while(l<r){ int mid=l+r>>1; if(a[mid]>=num) r=mid; else l=mid+1; } if(a[l]!=num){ System.out.println("-1 -1"); } //如果有这个数,再找右边界 else{ System.out.print(l+" "); l=0;r=n-1; while(l<r){ int mid=l+r+1>>1; if(a[mid]<=num) l=mid; else r=mid-1; } System.out.println(l); } } } }
原文链接:https://www.cnblogs.com/qdu-lkc/p/12184405.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- Maven 依赖范围、传递、排除,你确定你都清楚吗? 2020-06-02
- 第六章第三十七题(格式化整数)(Format an integer) - 编程 2020-05-26
- LeetCode 8. 字符串转换整数 (atoi) 2020-05-14
- LeetCode 面试题21. 调整数组顺序使奇数位于偶数前面 2020-05-05
- maven依赖范围 2020-05-03
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash