|
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