FindAnagramMappings [source code]

public class FindAnagramMappings {
static
/******************************************************************************/
class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        assert A.length == B.length;
        int[] res = new int[A.length];
        Map<Integer, Integer> map = new HashMap<> ();
        for (int i = 0; i < B.length; i++)
            map.put (B[i], i);
        for (int i = 0; i < res.length; i++)
            res[i] = map.get (A[i]);
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        FindAnagramMappings.Solution tester = new FindAnagramMappings.Solution();
    }
}

题目看完, 笨办法还是很简单的; 不过既然是Google的题目, 有没有什么更好的思路呢? 看了一下hint, 其实也是比较简单的一个做法;

如果是为了cheat OJ的话, 我感觉这题可以用sort的方法来做, 把B给sort了, 然后A一个一个的进行binary search就行了; 最后可能能打败用HashMap的这个思路; 不对, 这个思路有问题: 你对B进行sort之后, 你所有的number在B里面的index也整个都变化了, 这个你最后就没有办法找到原始的位置了;

最后的速度是9ms (NA), 没有什么暗坑.

题目的核心就是在preprocess的过程当中对B制作一个反向查询的结构, editorial也是这个思路, 没有什么太大的差别;

discussion也没有什么新奇的东西;

Problem Description

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.
Note:

• A, B have equal lengths in range [1, 100].
• A[i], B[i] are integers in range [0, 10^5].

Difficulty:Easy
Total Accepted:2K
Total Submissions:2.4K
Contributor:tinylic
Companies
google
Related Topics
hash table

Hint 1
Create a hashmap so that D[x] = i whenever B[i] = x. Then, the answer is [D[x] for x in A].