The Algorithm to Find Anagram Mappings between Two Arrays

  • 时间：2020-10-11 15:48:46
  • 分类：网络文摘
  • 阅读：98 次

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].

If the mapping index cannot be re-used (as there might be duplicates in the arrays), we need to maintain a vector of indices. The C++ code below illustrates the mapping algorithm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        unordered_map<int, vector<int>> table;
        for (int i = 0; i < B.size(); ++ i) {
            if (table.find(B[i]) == table.end()) {
                table[B[i]] = {i};
            } else {
                table[B[i]].push_back(i); // add duplicate index
            }
        }
        vector<int> r;
        for (int i = 0; i < A.size(); ++ i) {
            r.push_back(table[A[i]].back());  // pick a mapping index
            table[A[i]].pop_back();  // remove it from the queue
        }
        return r;
    }
};
class Solution {
public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
        unordered_map<int, vector<int>> table;
        for (int i = 0; i < B.size(); ++ i) {
            if (table.find(B[i]) == table.end()) {
                table[B[i]] = {i};
            } else {
                table[B[i]].push_back(i); // add duplicate index
            }
        }
        vector<int> r;
        for (int i = 0; i < A.size(); ++ i) {
            r.push_back(table[A[i]].back());  // pick a mapping index
            table[A[i]].pop_back();  // remove it from the queue
        }
        return r;
    }
};

The complexity is O(N) and the space complexity is O(N) as well. If the same index can be used to map duplicate numbers, the above can be simplified by using a hash map i.e. unordered_map in C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

The same anagram mapping algorithm can be implemented by Java using the HashMap i.e. O(N) both time and space complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        Map<Integer, Integer> D = new HashMap();
        for (int i = 0; i < B.length; ++i) {
            D.put(B[i], i);
        }
        int[] ans = new int[A.length];
        int t = 0;
        for (int x: A) {
            ans[t++] = D.get(x);
        }
        return ans;
    }
}
class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        Map<Integer, Integer> D = new HashMap();
        for (int i = 0; i < B.length; ++i) {
            D.put(B[i], i);
        }
        int[] ans = new int[A.length];
        int t = 0;
        for (int x: A) {
            ans[t++] = D.get(x);
        }
        return ans;
    }
}

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
5 Tips When Preparing for a Business Conference　 Customizing WordPress with Branda by WPMU DEV　 How to Blog Like Shakespeare　 Depth First Search Algorithm to Delete Insufficient Nodes in Roo　 C/C++ Program to Compute the Angle Between Hands of a Clock　 What Should Your Anti Virus Software Have in Order to Be Effecti　 The Importance of SEO and How They Improve the Number of Your Cl　 Learn The Basics Of Google My Business　 Iterative and Recursion Algorithms to Compute the Number of Step　 How to Check if a DLL or EXE is 32-bit or 64-bit (x86 or x64) us　
评论列表
添加评论