You are given two integer lists A and B of the same length.
List B is an anagram of list A, which means B contains exactly the same elements as A, but possibly in a different order.
Return an index mapping list P from A to B.
For every index i, P[i] = j means that the element A[i] appears at index j in B.
The lists may contain duplicate values. When a value appears multiple times, each occurrence in A must be matched with one unused occurrence of the same value in B.
When multiple unused matching indices exist in B, always choose the smallest unused index.
Class Definition
Implement the class AnagramIndexMapping.
Method Signature
List<Integer> anagramMappings(List<Integer> A, List<Integer> B)
- Returns a list
P where P[i] is an index in B.
B[P[i]] == A[i] must be true for every valid index i.
- Each index in
B must be used at most once.
- If duplicate values exist, match each occurrence in
A with the smallest unused matching index in B.
Input Format
The method receives two lists:
A: the original list of integers.
B: an anagram of A.
Output Format
Return a list of integers P with the same length as A.
For every index i, the value P[i] must be an index where A[i] can be found in B.
If the same value appears multiple times in B, its indices must be used from left to right.
Constraints
A.size() == B.size()
1 ≤ A.size(), B.size() ≤ 100
0 ≤ A[i], B[i] ≤ 100,000
B is an anagram of A.
Examples
Example 1
Method Call:
anagramMappings(A = [8, 3, 5, 1], B = [1, 5, 3, 8])
Output:
[3, 2, 1, 0]
Explanation:
A[0] = 8 appears at B[3], so P[0] = 3.
A[1] = 3 appears at B[2], so P[1] = 2.
A[2] = 5 appears at B[1], so P[2] = 1.
A[3] = 1 appears at B[0], so P[3] = 0.
Example 2
Method Call:
anagramMappings(A = [7, 7, 2, 9], B = [9, 7, 2, 7])
Output:
[1, 3, 2, 0]
Explanation:
The value 7 appears at indices 1 and 3 in B.
For A[0] = 7, the smallest unused matching index is 1, so P[0] = 1.
For A[1] = 7, index 1 is already used, so the smallest unused matching index is 3, and P[1] = 3.
The value 2 is mapped to index 2, and the value 9 is mapped to index 0.
Example 3
Method Call:
anagramMappings(A = [5, 1, 5, 1, 5], B = [1, 5, 5, 1, 5])
Output:
[1, 0, 2, 3, 4]
Explanation:
The value 5 appears at indices 1, 2, and 4 in B.
The three occurrences of 5 in A are mapped to 1, 2, and 4 in left-to-right order.
The value 1 appears at indices 0 and 3 in B.
The two occurrences of 1 in A are mapped to 0 and 3 in left-to-right order.
Example 4
Method Call:
anagramMappings(A = [4], B = [4])
Output:
[0]
Explanation:
There is only one element, and A[0] appears at B[0].