编号349:两个数组的交集
编号349:两个数组的交集
「说明:」
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
思路
注意题目特意说明:「输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序」
这道题用暴力的解法时间复杂度是O(n^2),那来看看使用哈希法进一步优化。
可以发现,貌似用数组做哈希表可以解决这道题目,把nums1的元素,映射到哈希数组的下表上,然后在遍历nums2的时候,判断是否出现过就可以了。
但是要注意,「使用数据来做哈希的题目,都限制了数值的大小,例如哈希表:可以拿数组当哈希表来用,但哈希值不要太大题目中只有小写字母,或者数值大小在[0- 10000] 之内等等。」
而这道题目没有限制数值的大小,就无法使用数组来做哈希表了。
「而且如果哈希值比较少、特别分散、跨度非常大,使用数组就造成空间的极大浪费。」
代码
public class 三四九题两个数组的交集 {
public static void main(String[] args) {
int [] num1 = {1,2,2,1};
int [] num2 = {2,2};
int[] arraryIntersect = arraryIntersectSort(num1, num2);
System.out.println(Arrays.toString(arraryIntersect));
}
//使用哈希法
public static int [] arraryIntersect(int [] num1, int [] num2){
HashMap<Integer,Integer> map = new HashMap<>();
List<Integer> list = new ArrayList<>();
for(int num : num1){
if( !map.containsKey(num) ){
map.put( num,1 );
}else{
map.put( num,map.get(num)+1 );
}
}
for( int num : num2){
if( map.containsKey( num )){
map.put( num, map.get(num)-1);
if( map.get(num) == 0 ){
map.remove( num );
list.add( num );
}
}
}
int res [] =new int [list.size()];
for( int i = 0; i < list.size(); i++ ){
res[i] = list.get(i);
}
return res;
}
//使用排序的方法利用双指针
public static int [] arraryIntersectSort(int [] num1, int [] num2){
List<Integer> list = new ArrayList<>();
Arrays.sort( num1 );
Arrays.sort( num2 );
int p1 = 0;
int p2 = 0;
while( p1 < num1.length && p2 < num2.length ){
if( num1[p1] == num2[p2]) {
list.add( num1[p1] );
p1++;
p2++;
}else if( num1[p1] < num2[p2] ){
p1++;
}else{
p2++;
}
}
int res [] =new int [list.size()];
for( int i = 0; i < list.size(); i++ ){
res[i] = list.get(i);
}
return res;
}
}
0条评论