760 Find Anagram Mappings

760. Find Anagram Mappings

1. Question

Given two listsAandB, andBis an anagram ofA.Bis an anagram ofAmeansBis made by randomizing the order of the elements inA.

We want to find anindex mappingP, fromAtoB. A mappingP[i] = jmeans theith element inAappears inBat indexj.

These listsAandBmay 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]

asP[0] = 1because the0th element ofAappears atB[1], andP[1] = 4

because the1st element ofAappears atB[4], and so on.

Note:

1. A, Bhave equal lengths in range[1, 100].

2. A[i], B[i]are integers in range[0, 10^5].

2. Implementation

(1)Hash Table

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        if (A.length != B.length) {
            return new int[0];
        }

        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 < A.length; i++) {
            res[i] = map.get(A[i]);
        }
        return res;
    }
}

3. Time & Space Complexity

Hash Table: 时间复杂度O(n)，空间复杂度O(n)