760 Find Anagram Mappings

Search…

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
1
A = [12, 28, 46, 32, 50]
2
B = [50, 12, 32, 46, 28]
Copied!
We should return
1
[1, 4, 3, 2, 0]
Copied!
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
1
class Solution {
2
    public int[] anagramMappings(int[] A, int[] B) {
3
        if (A.length != B.length) {
4
            return new int[0];
5
        }
6
​
7
        int[] res = new int[A.length];
8
        Map<Integer, Integer> map = new HashMap<>();
9
​
10
        for (int i = 0; i < B.length; i++) {
11
            map.put(B[i], i);
12
        }
13
​
14
        for (int i = 0; i < A.length; i++) {
15
            res[i] = map.get(A[i]);
16
        }
17
        return res;
18
    }
19
}
Copied!
3. Time & Space Complexity
Hash Table: 时间复杂度O(n)，空间复杂度O(n)

749 Shortest Completing Word

Trie

Last modified 2yr ago

Copy link

Contents

760. Find Anagram Mappings

1. Question

2. Implementation

3. Time & Space Complexity

760. Find Anagram Mappings​

1. Question

2. Implementation

3. Time & Space Complexity

760. Find Anagram Mappings