1
2
3
4
5
6
|
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
|
题意:求两个数组的交集,每个元素可以出现多次,返回的数组顺序随意。
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
|
public
class
Solution {
public
int
[] intersect(
int
[] nums1,
int
[] nums2) {
List<Integer> list=
new
ArrayList<Integer>();
int
length1=nums1.length;
int
length2=nums2.length;
int
[] ret=
new
int
[Math.min(length1,length2)];
int
index=
0
;
HashMap<Integer,Integer> map=
new
HashMap<Integer,Integer>();
for
(
int
i=
0
;i<length1;i++){
if
(!map.containsKey(nums1[i])){
map.put(nums1[i],
1
);
}
else
{
map.put(nums1[i],map.get(nums1[i])+
1
);
}
}
for
(
int
i=
0
;i<length2;i++){
if
(map.containsKey(nums2[i]) && map.get(nums2[i])!=
0
){
map.put(nums2[i],map.get(nums2[i])-
1
);
ret[index++]=nums2[i];
}
}
return
Arrays.copyOfRange(ret,
0
,index);
}
}
|
PS:
1、先申请一个长度是较小长度的数组的数组。
2、用hashmap存放第一个数组的各个数字出现的次数。
3、遍历第二个数组,去hashmap中找,如出现,则hashmap对应的次数减1,同时将key加入到数组中。
4、最后取部分返回。。。
本文转自 努力的C 51CTO博客,原文链接:http://blog.51cto.com/fulin0532/1891688