The Algorithm to Find Anagram Mappings between Two Arrays

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

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) —

推荐阅读：
How to Reverse Words in a String?　 Design a Logger Rate Limiter in C++/Java　 C++ Coding Exercise: Smallest Range of Array　 Coding For Profit: 4 Types Of Websites To Consider Building　 How to Compute the Projection Area of 3D Shapes?　 How To Find The Ideal Monitor For Coders?　 How to Partition an Array Into Three Parts With Equal Sum?　 Compute the Sum of Even Numbers After Queries　 How to Compute Nested List Weight Sum of Any Arrays?　 7 Laws Every Blogger Must Know to Avoid Lawsuits　
评论列表
添加评论