GuilinDev

Lc0760

05 August 2008

760 Find Anagram Mappings

原体概述

Given two lists 

1

A
and 
1

B
, and 
1

B
is an anagram of 
1

A
. 
1

B
is an anagram of 
1

A
means 
1

B
is made by randomizing the order of the elements in 
1

A
.

We want to find an index mapping 

1

P
, from 
1

A
to 
1

B
. A mapping 
1

P[i] = j
means the 
1

i
th element in 
1

A
appears in 
1

B
at index 
1

j
.

These lists 

1

A
and 
1

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 

1

P[0] = 1
because the 
1

0
th element of 
1

A
appears at 
1

B[1]
, and 
1

P[1] = 4
because the 
1

1
st element of 
1

A
appears at 
1

B[4]
, and so on.

Note:

  1. 1

    A, B
    have equal lengths in range 
    1

    [1, 100]
    .
  2. 1

    A[i], B[i]
    are integers in range 
    1

    [0, 10^5]
    .

题意和分析

给两个整型数组，它们之间是anagrams，找出第一个数组中的元素在第二个数组出现的索引的位置。暴力搜索就是n^2，如果先把数组B的元素放入到一个hashmap里面，元素值为key，索引为value，然后对A的每个元素进行寻找，因为HashMap的get()方法是在hashcode不碰撞的情况下是O(1)的，(如果最坏情况全部元素都是碰撞的，那就退化成线性时间复杂度)，所以整个时间复杂度是O(2n)；

另外这道题并没有说数组中的元素是否可以是重复的，如果用HashMap来解，会出现key相同（value索引值不同）的情况，我们不希望遇到同样值的情况下只取到同一个索引值的情况，需要做特殊处理。

代码

不考虑重复值的简单解法，也可以AC

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

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        if (A == null || B == null || A.length == 0 || B.length == 0) {
            return new int[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
        int[] result = new int[A.length];
        //把数组B中元素放入到map中
        for (int i = 0; i < B.length; i++) {
            map.put(B[i], i);
        }

        //遍历A数组
        for (int i = 0; i < A.length; i++) {
            result[i] = map.get(A[i]);
        }
        return result;
    }
}

考虑重复值

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

class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
        if (A == null || B == null || A.length == 0 || B.length == 0) {
            return new int[0];
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        int[] result = new int[A.length];
        //把数组B中元素放入到map中
        for (int i = 0; i < B.length; i++) {
            map.computeIfAbsent(B[i], k -> new ArrayList<>()).add(i);//如果map里没有B[i]这个key，那么就按照后面的这个function添加对应的key和value，如果有这个key，那么就不添加，这个方法避免了hashcode值碰撞
        }

        //遍历A数组
        for (int i = 0; i < A.length; i++) {
            result[i] = map.get(A[i]).remove(map.get(A[i]).size() - 1);//找到第一个key后加入到result中并从map中删除
        }
        return result;
    }
}
This site is open source. Improve this page.