760.找出变位映射

760.找出变位映射

付费题。

Given two lists Aand B, and B is an anagram of A. B is an anagram of A means B is made by randomizing the order of the elements in A.

We want to find an index mapping P, from A to B. A mapping P[i] = j means the ith element in A appears in B at index j.

These lists A and B may contain duplicates. If there are multiple answers, output any of them.

For example, given

A = [12, 28, 46, 32, 50]

B = [50, 12, 32, 46, 28]

We should return

[1, 4, 3, 2, 0]

as P[0] = 1 because the 0th element of A appears at B[1], and P[1] = 4 because the 1st element of A appears at B[4], and so on.

思路:因为有重复元素,用multimap. 将数组B写入multimap,key为元素,value为下标.记为bmap.对A中每一个元素A[i],在bmap中查找A[i]在B中的下标,然后赋值给P[i]即可. (注意multimap与map的不同用法,如插入,查找等)

class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        multimap<int, int> bmap;//B的对应map
        vector<int> P(A.size(), 0);//输出,与A,B等长,初始化为0
        for (int i = 0; i < B.size(); i++) {
            bmap.insert(make_pair(B[i], i));//将B映射到bmap
        }
        for (int i = 0; i < A.size(); i++) {//对A中所有元素
            auto p = bmap.equal_range(A[i]);//在bmap中找key为A[i]的键值对(可能有多个)
            for (auto it = p.first; it != p.second; it++) {//用迭代器遍历所有key相同的键值对
                P[i] = it->second;//键值对(本质上是一个pair类型)的second域即为A[i]在B中的下标.
            }
        }
        return P;
    }
};