一道题:求两个集合的交集,元素可重复。如 {1,2,2,3},{1,2} =〉{1,2};{1,2,2,3},{1,2,2} =〉{1,2,2}。

概要设计

  我想到使用 MapReduce 的思维统计出集合中元素及元素出现的次数——Map< K,V>,K:集合元素;V:元素出现的次数。最后遍历整个 Map,K 作为集合的元素,V 作为该元素的数量保存在List中。

详细设计

  • map
    list1:[1,2,2,3] -> map1:{1=1, 2=2, 3=1}
    list2:[1,2,2,2,4] -> map2:{1=1, 2=3, 4=1}

  • reduce
      多个map的 K 交集,V 取最小的。
    map1:{1=1, 2=2, 3=1},map2:{1=1, 2=3, 4=1} -> map3:{1=1, 2=2}

  • list
    map3:{1=1, 2=2} -> list3:[1, 2, 2]

编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
@org.junit.Test public void listsMerge()
{
List<Integer> list1 = new ArrayList();
List<Integer> list2 = new ArrayList();
List<Integer> list3 = new ArrayList();

list1.add(1);
list1.add(2);
list1.add(2);
list1.add(3);

list2.add(1);
list2.add(2);
list2.add(2);
list2.add(2);
list2.add(4);

Map<Integer, Integer> map1 = new HashMap<>();
Map<Integer, Integer> map2 = new HashMap<>();
Map<Integer, Integer> map3 = new HashMap<>();

// 时间复杂度 O(n)
for (Integer e : list1)
{
if (map1.containsKey(e))
{
map1.put(e, map1.get(e) + 1);
} else
{
map1.put(e, 1);
}
}

// 时间复杂度 O(m)
System.out.println("map1:" + map1.toString());

for (Integer e : list2)
{
if (map2.containsKey(e))
{
map2.put(e, map2.get(e) + 1);
} else
{
map2.put(e, 1);
}
}

System.out.println("map2:" + map2.toString());

// 时间复杂度 O(n*m)
for (Map.Entry entry1 : map1.entrySet())
{
for (Map.Entry entry2 : map2.entrySet())
{
if (entry1.getKey() == entry2.getKey())
{
Integer key = Integer.parseInt(entry1.getKey().toString());
Integer value1 = Integer.parseInt(entry1.getValue().toString());
Integer value2 = Integer.parseInt(entry2.getValue().toString());
map3.put(key, value1 < value2 ? value1 : value2);

}
}
}

System.out.println("map3:" + map3.toString());

// 时间复杂度 O(j*k)
for (Map.Entry entry : map3.entrySet())
{
for (int i = 0; i < Integer.parseInt(entry.getValue().toString()); i++)
{
list3.add(Integer.parseInt(entry.getKey().toString()));
}
}

System.out.println("list3:" + list3.toString());

}