三种不同的解法,第一种最快,第二种和第三种更具普遍性(当数很大时)。
解法一:预处理
#时间复杂度o(n),空间复杂度o(M) M为输入数的最大值
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int max = 1e9+7;
typedef long long int ll;
int n,q;
int num[100005];
int start[10005],last[10005];
int main()
{
scanf("%d %d",&n,&q);
for(int i = 0;i < 10005;i++)
{
start[i] = -1;
last[i] = -1;
}
for(int i = 0;i < n;i++)
{
scanf("%d",&num[i]);
if(start[num[i]] == -1) start[num[i]] = i;
last[num[i]] = i;
}
for(int i = 0;i<q;i++)
{
int t;
scanf("%d",&t);
printf("%d %d\n",start[t],last[t]);
}
return 0;
}
解法二:二分+线性探测
#时间o(n),空间o(1)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int max = 1e9+7;
typedef long long int ll;
int n,q;
int num[100005];
int b=-1,l=-1;
void bin_search(int key)
{
int i = 0, j = n-1,m;
while(i <= j)
{
m = (i+j)/2;
if(num[m] > key) j = m-1;
else if(num[m] < key) i = m+1;
else break;
}
if(num[m] == key)
{
b = m,l = m;
while(b-1 >= 0 && num[b-1] == key) b--;
while(l+1 <= n-1 && num[l+1] == key) l++;
}
}
int main()
{
scanf("%d %d",&n,&q);
for(int i = 0;i < n;i++)
scanf("%d",&num[i]);
for(int i = 0;i<q;i++)
{
int t;
b=-1,l=-1;
scanf("%d",&t);
bin_search(t);
printf("%d %d\n",b,l);
}
return 0;
}
解法三:二分+二分
#时间o(n),空间o(1)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int max = 1e9+7;
typedef long long int ll;
int n,q;
int num[100005];
int b=-1,l=-1;
int bin_search_less(int key)
{
int l = 0, r = n-1;
while(l < r)
{
int mid = l+r >> 1;
if(num[mid] < key) l = mid+1;
else r = mid;
}
return l;
}
int bin_search_more(int key)
{
int l = 0, r = n-1;
while(l < r)
{
int mid = l+r+1 >> 1; // 若mid = l+r>>2,则 当数据为 2 2 时,陷入死循环
if(num[mid] <= key) l = mid; // 原理为,(1+0)/2 = 0,为向下取整,加1改为向上取整即可
else r = mid-1;
}
return l;
}
int main()
{
scanf("%d %d",&n,&q);
for(int i = 0;i < n;i++)
scanf("%d",&num[i]);
for(int i = 0;i<q;i++)
{
int t;
scanf("%d",&t);
b = bin_search_less(t);
if(num[b] != t)
{
printf("-1 -1\n");
continue;
}
l = bin_search_more(t);
printf("%d %d\n",b,l);
}
return 0;
}