760. Find Anagram Mappings

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]

as P[0] = 1because the0th element ofAappears atB[1], andP[1] = 4because 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].

Thoughts:1

1. (K,V) : (value, list of (index of B))

2. get the value of A[i], retrieve the last element from the mapped list

Code

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        int [] result = new int [A.length];
        Map<Integer, List<Integer>> map = new HashMap<>();
        for( int i = 0; i < B.length; i++){
            map.computeIfAbsent(B[i], k->new ArrayList<>()).add(i);
        }

        for( int i = 0; i < A.length; i++){
            result[i] = map.get(A[i]).remove(map.get(A[i]).size() - 1);
        }

        return result;
    }
}

from diddit's post

Use Sorting:

public int[] anagramMappings(int[] A, int[] B) {
    int n = A.length;
    for(int i = 0; i < n; i++) {
        A[i] = (A[i] << 8) + i;
        B[i] = (B[i] << 8) + i;
    }
    Arrays.sort(A);
    Arrays.sort(B);
    int[] ans = new int[n];
    for(int i = 0; i < n; i++)
        ans[A[i] & 0xFF] = B[i] & 0xFF;
    return ans;
}

from tyuan73's post

class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        vector<int> result;
        unordered_multimap<int, int> m;
        for(int i = 0; i < B.size(); i++){
            m.emplace(B[i],i);
        }
        for(int i: A){
            auto iter = m.find(i);
            result.push_back(iter->second); // iter->first: value from B; iter->second: associated index in B
            // cout<<"iter->first: "<<(iter->first)<<"; iter->second: "<<(iter->second)<<endl;
            m.erase(iter);
        }

        return result;
    }
};

from PuckDuck's post

fastest C++:

int hashFn(int input) {
    return input % 100;
}

class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        unordered_map<int, int> bHash;
        vector<int> P;
        for (int i = 0; i < B.size(); i++) {
            bHash[B[i]] = i;
        }
        for (int i = 0; i < A.size(); i++) {
            P.push_back(bHash[A[i]]);
        }

        return P;
    }
};

fastest Java

/*
    A = [1,3,2]
    B = [1,2,3]
    output = [0,2,1]
*/
class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        int[] ret = new int[A.length];
        for (int i = 0 ; i < ret.length ; i++) {
            ret[i] = indexOf(B, A[i]);
        }
        return ret;
    }

    private int indexOf(int[] target, int value) {
        for (int i = 0 ; i < target.length; i++) {
            if (target[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

fastest Python

class Solution(object):
    def anagramMappings(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: List[int]
        """
        # mapped to the same index of B if duplicates exist
        C = {x : i for i, x in enumerate(B)}

        return [C[x] for x in A]