789数的范围
问题描述
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 0 开始计数)。
如果数组中不存在该元素,则返回 -1 -1。
原题链接:https://www.acwing.com/problem/content/791/
输入格式
- 第一行包含整数 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
我的题解
#include<iostream>
using namespace std;
int num, n_q;
int arr[100010];
int q[10010];
int minx, maxx;
void find(int q, int l, int r) {
for (int i = l; i <= r; i++) {
if (arr[i] == q) {
minx = i;
break;
}
}
for (int i = r; i >= l; i--)
{
if (arr[i] == q) {
maxx = i;
break;
}
}
}
void query(int q, int l, int r) {
if (l == r) {
if(arr[l]==q) {
maxx = minx = l;
}
return;
}
int mid = (l + r) / 2;
if (q < arr[mid]) query(q, l, mid);
if (q > arr[mid]) query(q, mid + 1, r);
if (q == arr[mid]) find(q, l, r);
}
int main() {
cin >> num >> n_q;
for (int i = 0; i < num; i++) {
cin >> arr[i];
}
for (int i = 0; i < n_q; i++) {
cin >> q[i];
}
for (int i = 0; i < n_q; i++) {
maxx = -1; minx = num;
query(q[i], 0, num - 1);
if (maxx == -1) {
minx = -1;
}
cout << minx << " " << maxx << endl;
}
return 0;
}
运用了类似归并的思想,刚开始的做法超时,于是加上了当数字串中相同元素较多时的解决方法。
789数的范围
http://example.com/2023/03/09/789数的范围/