两种做法,一种是自己瞎写的,一种是大佬上课时候讲的。
算法一:暴力做法
时间复杂度:O(q*n) 1e+9过不了超时了。
代码如下:
#include<iostream>
using namespace std;
const int N = 100010;
int n, q, k;
int a[N];
int main()
{
cin >> n >> q;
for (int i = 0; i < n; i++)
cin >> a[i];
while (q--)
{
cin >> k;
int left = -1, right = -1;
for (int i = 0; i < n; i++)
{
if (k == a[i])
{
left = i;
break;
}
}
for (int i = n - 1; i >= 0; i--)
{
if (k == a[i])
{
right = i;
break;
}
}
cout << left << " " << right << "\n";
}
return 0;
}
算法二:二分查找
时间复杂度:O(q*logn)这样就可以过了,大概是1e+7.
代码如下:
#include<iostream>
using namespace std;
const int N=100010;
int n,m,k;
int q[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>q[i];//先读入数据据
while(m--)
{
cin>>k;
int l=0,r=n-1;
while(l<r)
{
int mid=l+r>>1;
if(q[mid]>=k) r=mid;
else l=mid+1;
}//先找到左边端点
if(q[l]!=k) //没有找到左端点
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]<=k) l=mid;
else r=mid-1;
}
cout<<r<<endl;//输出右端点
}
}
return 0;
}
前面的第一个while是寻找左边界,如果找到了左边界,就先输出左边界,再查找右边界,如果连左边界都没有找到,说明这个数并不在数组里面,就直接输出“ -1 -1 ”。
注意:查找左边界前面的mid是不需要加1的,而查找右边界,mid是需要加上1的,可以这样记忆,右边界一般都比左边界要大,所以就需要加上一个1。
二分查找的简单推演(k=3为例):
0 1 2 3 4 5
1 2 2 3 3 4
k=3
左端点:
l=0,r=5 mid=2 l=3
l=3,r=5 mid=4 r=4
l=3,r=4 mid=3 r=3
l=r=3
右端点:
l=0,r=5 mid=3 l=3
l=3,r=5 mid=4 l=4
l=4,r=5 mid=5 r=4
l=r=4