1 描述
给定一个经过升序排序后的数组,以及一个闭区间[a,b]
要求按升序输出给定数组在[a,b]区间内的所有数。
输入描述
第一行为数的个数n
第二行为n个按升序给出的数
第三行两个数a,b 表示区间[a,b]
n范围为[1,1000000]
输入数字范围为[1,1000000000]
输出描述
按升序输出在区间内的数,每行一个数字
如果没有数字在区间内,则输出"No Result!" (引号去掉)
测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
---|---|---|---|---|---|
测试用例 1 |
以文本方式显示
|
以文本方式显示
|
1秒 | 64M | 0 |
测试用例 2 |
以文本方式显示
|
以文本方式显示
|
1秒 | 64M | 0 |
测试用例 3 |
以文本方式显示
|
以文本方式显示
|
1秒 | 64M | 0 |
2 解题
(1)二分法
- 有序数组中找到与a和b条件符合的下标,瞬间想到了二分法,但是写了一会发现下标的边界处理比较麻烦,然后舍弃了这种方法
(2)直接遍历
- 既然已经是排好序的数组,直接扫描一遍,遇到的时候就返回这个下标
- 代码
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
long int findindex(long int data[],long int begin,long int key,long int end){
for(long int i=0;i<=end;i++){
if(data[i]>=key)
return i;
}
}
int main(int argc,char *argv[]){
//freopen("file in.txt","r",stdin);
long int n;
long int *data;
long int index1,index2;
long int i;
long int a,b;
cin>>n;
data=(long int*)malloc(sizeof(long int)*n);
for(i=0;i<n;i++){
cin>>data[i];
}
cin>>a>>b;
// boundary
if(a>data[n-1]||b<data[0]||a>b){
cout<<"No Result!"<<endl;
return 0;
}
if(a<=data[0])
index1=0;
else
index1 = findindex(data,0,a,n-1);
if(b>=data[n-1])
index2=n-1;
else
index2 = findindex(data,index1,b,n-1);
//boundary
//上面boundary里面的条件语句是考虑一些可以不需要进入遍历函数的情况
// 两个边界使用的是同一个函数,实际上他们是有细微区别的
while(data[index2+1]==b){
index2++;
}
if(data[index2]>b){
index2-=1;
}
if(index2<index1)
cout<<"No Result!"<<endl;
else
for(i=index1;i<=index2;i++){
cout<<data[i]<<endl;
}
return 0;
}
- 小结
- a和b分别是需要输出数据的左右边界,使用同一个函数来遍历查找的话需加以处理
查找匹配b的时候得到的下标对应的data[index2]的值可能是大于b的,不需要输出
if(data[index2]>b){
index2-=1;
}
- 自定义函数findindex里面遇到第一个大于或者等于key的值就会返回,可能会导致漏掉一些数
比如这种输入案例
6
5 6 7 8 8 9
4 8
这样只会输出一个8
- 增加一个处理的语句
while(data[index2+1]==b){
index2++;
}
- 查找完index1之后查找index2的话并不需要再从头遍历一次,因为经过前面if结构的排除,index2一定在index1的右边(也可能是同一个位置),那么前面的0到index1的部分第一次查找完毕的时候直接扔掉了,符合**减治法**的思想
(3)使用lower_bound()和upper_bound()函数
- 头文件 #include<algorithm>
- 相关知识
- 非降序数组
lower_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个 大于或等于 num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 |
---|
pper_bound( begin,end,num):从数组的begin位置到end-1位置二分查找第一个 大于 num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 |
- 降序数组,重载lower_bound()和upper_bound()
lower_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 |
---|
upper_bound( begin,end,num,greater() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字,找到返回该数字的地址,不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。 |
- 代码
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(int argc,char *argv[]){
// freopen("file in.txt","r",stdin);
long int n;
long int *data;
long int index1,index2;
long int i;
long int a,b;
cin>>n;
data=(long int*)malloc(sizeof(long int)*n);
for(i=0;i<n;i++){
cin>>data[i];
}
cin>>a>>b;
if(a>data[n-1]||b<data[0]||a>b){
cout<<"No Result!"<<endl;
return 0;
}
if(a<=data[0])
index1=0;
else
index1 = lower_bound(data,data+n,a)-data;
// lower_bound()函数返回的是地址
if(b>=data[n-1])
index2=n-1;
else
index2 = upper_bound(data+index1,data+n,b)-data;
if(data[index2]>b){ //为了方便闭区间输出
index2-=1;
}
if(index2<index1)
cout<<"No Result!"<<endl;
else
for(i=index1;i<=index2;i++){
cout<<data[i]<<endl;
}
return 0;
}
- 该函数返回的是地址,减去首地址(数组名)就可以得到下标
- 有序数组才有意义