4.3　在数组中快速查找指定元素

在1.4节中给出了一种快速查找指定元素的二分法，但使用二分法需预先对序列中的数据进行排序，并按下述方法递归查找：由序列的中间元素划分出左右子序列。每次待查找元素与中间元素比较大小，确定该元素是否为中间元素或者可能属于哪个子序列内的元素。这个过程一直进行到找到待查元素位置或子区间不存在为止，二分查找可使得计算效率提高到O(log(n))。

但是，若序列中的数据重复出现，并且要避免预先排序的额外开销，要求按照出现次数给出被查数据的位置，怎么办？

使用vector类的动态数组不需要进行排序和递归，较为简便。下面，我们就通过一个实例来详述这种方法。

【4.3.1　Easy Problem from Rujia Liu?】

给出一个数组，请找到一个整数v的第k次出现（从左至右）。为了使问题更加困难、更加有趣，请回答m个这样的查询。

输入

输入给出若干测试用例。每个测试用例的第一行给出两个整数n、m(1≤n,m≤100 000)，表示数组中元素的个数和查询的数目。下一行给出不大于1 000 000的n个正整数。接下来的m行每行给出两个整数k和v(1≤k≤n,1≤v≤1 000 000)。输入以EOF结束。

输出

对于每个查询，输出出现的位置（数组起始位置为1）。如果没有这样的元素，则输出'0'。

试题来源：Rujia Liu’s Present 3:A data structure contest celebrating the 100th anniversary of Tsinghua University

在线测试：UVA 11991

试题解析

本题要求按照出现次数查找指定元素值的下标位置。最为简便的计算方法是，使用vector类的动态数组存储每个整数值的下标位置。

设动态数组v[]，其中v[x]按照输入顺序依次存储整数x的下标位置，即v[x][k-1]存储第k次出现x的下标位置，v[x].size()是原数组中x的最多出现次数。

在输入数组的同时构造动态数组v[]：若输入数组的第i个元素x，则通过v[x].push_back(i)将其下标序号i送入容器v[x]（1≤i≤n）；v[]以原数组的元素值作为下标，数组元素为一个“容器”，依次存放该整数值的下标。

显然，每次查询可直接在这个记录表中找到结果，无须顺序查找或二分查找，时间复杂度为O(1)。若第j个查询是第k次出现x的下标位置（1≤j≤m），则分析：若v[x].size()<k，则说明x的出现次数不足k次，输出0；否则输出数组中第k次出现x的下标位置v[x][k-1]。

参考程序

---

#include<iostream>
#include<vector>
using namespace std;
const int MAXX=1000050;
vector<int> v[MAXX];
int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)==2)             //反复输入元素数和查询数
    {
        for (int i=1;i<MAXX;i++) v[i].clear(); //动态数组初始化为空
        for (int i=1;i<=n;i++)                 //输入原数组，构建动态数组
        {
            int x;
            scanf("%d",&x);                    //输入第i个元素值x
            v[x].push_back(i);                 //将x的下标序号i送入容器v[x]
        }
        for (int i=1;i<=m;i++)                 //依次处理每个查询
        {
            int k,x;
            scanf("%d%d",&k,&x);               //第i个查询是第k次出现x的下标位置
            int ans=0;                         //下标位置初始化为0
            if (v[x].size()<k) ans=0;          //若x的出现次数不足k次，则输出0
                else ans=v[x][k-1];            //否则记下第k次出现x的下标位置
            printf("%d\n",ans);                //输出第k次出现x的下标位置
        }
    }
    return 0;
}

---