题目大意：输出数组A中每个元素在数组B中的索引。
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
|
1 2 |
A = [12, 28, 46, 32, 50] B = [50, 12, 32, 46, 28] |
We should return
|
1 |
[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 Aappears at B[4], and so on.
Solution:
C++
Time complexity: O(nlogn)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua // Running time: 6 ms class Solution { public: vector<int> anagramMappings(vector<int>& A, vector<int>& B) { map<int, int> indices; for (int i = 0; i < B.size(); ++i) indices[B[i]] = i; vector<int> ans; for (const int a : A) ans.push_back(indices[a]); return ans; } }; |
C++ / No duplication
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 6 ms class Solution { public: vector<int> anagramMappings(vector<int>& A, vector<int>& B) { map<int, vector<int>> indices; for (int i = 0; i < B.size(); ++i) indices[B[i]].push_back(i); vector<int> ans; for (const int a : A) { ans.push_back(indices[a].back()); indices[a].pop_back(); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment