一道简单题( East Problem from Rujia Liu 11991Uva)(数据结构)(锻炼思维好题)

时间:2022-06-28 10:28:12

数据结构好题。

题目:

给出一个包含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;
}