跳转至

760. 找出变位映射 🔒

题目描述

给你两个整数数组 nums1 和 nums2，其中 nums2 是 nums1 的一个 变位词 。两个数组都可能包含重复元素。

返回一个下标映射数组 mapping，它将 nums1 映射到 nums2，其中 mapping[i] = j 表示 nums1 中的第 i 个元素出现在 nums2 的第 j 个下标上。如果有多个答案，返回 任意一个 。

数组 a 是数组 b 的一个 变位词 意味着 b 是通过将 a 中元素的顺序随机打乱生成的。

 

示例 1：

输入：nums1 = [12,28,46,32,50], nums2 = [50,12,32,46,28]
输出：[1,4,3,2,0]
解释：因为 nums1 中的第 0 个元素出现在 nums2[1] 上，所以 mapping[0] = 1，而 nums1 中的第 1 个元素出现在 nums2[4] 上，所以 mapping[1] = 4，以此类推。

示例 2：

输入：nums1 = [84,46], nums2 = [84,46]
输出：[0,1]

 

提示：

  • 1 <= nums1.length <= 100
  • nums2.length == nums1.length
  • 0 <= nums1[i], nums2[i] <= 105
  • nums2 是 nums1 的一个变位词。

解法

方法一：哈希表

思考

两数组互为变位词，求 \(nums1\) 各元素在 \(nums2\) 中的一个下标。长度 \(100\)，对每个值扫描也可以，哈希一次即可 \(O(n)\)。

先记下 \(nums2\) 中每个值的下标（后者覆盖前者即可），再按 \(nums1\) 取值。题目允许任意合法映射。

我们用一个哈希表 \(\textit{d}\) 来存储数组 \(\textit{nums2}\) 中每个元素及其对应的下标。然后我们遍历数组 \(\textit{nums1}\)，对于每个元素 \(\textit{nums1}[i]\)，我们从哈希表 \(\textit{d}\) 中获取其对应的下标并存入结果数组中。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)，其中 \(n\) 是数组的长度。

1
2
3
4
class Solution:
    def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
        d = {x: i for i, x in enumerate(nums2)}
        return [d[x] for x in nums1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    public int[] anagramMappings(int[] nums1, int[] nums2) {
        int n = nums1.length;
        Map<Integer, Integer> d = new HashMap<>(n);
        for (int i = 0; i < n; ++i) {
            d.put(nums2[i], i);
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = d.get(nums1[i]);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        unordered_map<int, int> d;
        for (int i = 0; i < n; ++i) {
            d[nums2[i]] = i;
        }
        vector<int> ans;
        for (int x : nums1) {
            ans.push_back(d[x]);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func anagramMappings(nums1 []int, nums2 []int) []int {
    d := map[int]int{}
    for i, x := range nums2 {
        d[x] = i
    }
    ans := make([]int, len(nums1))
    for i, x := range nums1 {
        ans[i] = d[x]
    }
    return ans
}

1
2
3
4
5
6
7
function anagramMappings(nums1: number[], nums2: number[]): number[] {
    const d: Map<number, number> = new Map();
    for (let i = 0; i < nums2.length; ++i) {
        d.set(nums2[i], i);
    }
    return nums1.map(num => d.get(num)!);
}

评论