数据结构好题。
题目:
给出一个包含n个整数的数组,你需要回答若干个询问。每次询问两个整数k和v;(1<=k<=n,1<=v<=10^6)
输出从左向右第k个v的下标。。
本题有很多做法,我们希望有一种数据结构,直接读取data[v][k].就是答案
我们尝试着构造,这种数据结构不难理解,直接上代码,慢慢琢磨好吗?
思路:没输入一个数x。判断是否在data[i]出现,如果出现,直接将他加入到data[i][cur]下一个位置,并保存x的下标。 如果没有出现,则重新建一个data[x], data[x][0]=(x的下标)
data[x][cur] :表示x出现第cur+1次的下标
那么题目的答案就是 data[v][k-1];
#include"cstdio" #include"cstdlib" #include"algorithm" #include"cstring" #include"iostream" #include<map> #include"vector" using namespace std; map<int ,vector<int> >a; //可以理解为不定长二维数组 int main() { int n,m,x,y; while(scanf("%d%d",&n,&m)==2) //n个数m次查询 { for(int i=0;i<n;i++) { scanf("%d",&x); if(!a.count(x)) //判断x是否在容器里 a[x]=vector<int>(); //没有则新建一个 a[x].push_back(i+1); //将对应的下标保存起来 } while(m--) //进行m次查询 { int k,v; scanf("%d%d",&k,&v); if(!a.count(v)||a[v].size()<k) //如果不存在v 或者v出现的次数小于k cout<<"0"<<endl; else cout<<a[v][k-1]<<endl; } } return 0; }