LintCode第547题-两数组的交集
描述
给出两个数组，写出一个方法求出它们的交集
结果中的每个元素必须是唯一的
例1:
输入: nums1 = [1, 2, 2, 1], nums2 = [2, 2],
输出: [2].例2:
输入: nums1 = [1, 2], nums2 = [2],
输出: [2].挑战
可以用三种不同的方法实现吗？
思路:由于元素必须唯一 那么我们立即想到Set 和map集合类 其中结果要求返回仅仅是去重数字 所以用Set方法最高效去重
主要步骤是1 去重 2 比较相等并记录返回
代码如下:
public class Solution {
/**
* @param nums1: an integer array
* @param nums2: an integer array
* @return: an integer array
* we will sort your return value in output
*/
public int[] intersection(int[] nums1, int[] nums2) {
// write your code here
//两个循环
int m=nums1.length;
int n=nums2.length;
int[] nums3 = new int[m];
Set<Integer> nums1Set=new HashSet<>();
Set<Integer> nums2Set=new HashSet<>();
//去重
for (int x : nums1)
{
nums1Set.add(x);
}
for (int y : nums2)
{
nums2Set.add(y);
}
int Index=0;
int nums3Length=0;
// 【新增】先数一遍真实交集个数（保持你的双循环+break 结构）
for (Integer eachNums1 : nums1Set) {
Integer temp = eachNums1;
for (Integer eachNums2 : nums2Set) {
if (temp.equals(eachNums2)) {
nums3Length++;
break;
}
}
}
//拿出对应的元素
nums3=new int[nums3Length];
for(Integer eachNums1:nums1Set)
{
Integer temp=eachNums1;
for(Integer eachNums2:nums2Set)
{
if(temp.equals(eachNums2))
{
nums3[Index++]=temp;
break;
}
}
}
return nums3;
}
}
其中比较相等为双层for循环所以 时间复杂度为O(m*n)
如果要优化后的
那么关键在于 把第二次循环变为了哈希查找 时间复杂度变为了O(m+n) 为什么会变成这样 因为
哈希分布时几乎总是 O(1)
代码如下:
import java.util.*;
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) return new int[0];
Set<Integer> nums1Set = new HashSet<>();
Set<Integer> nums2Set = new HashSet<>();//下面两句时间复杂度为O(m+n)
for (int x : nums1) nums1Set.add(x);
for (int y : nums2) nums2Set.add(y);
// 选小集合作为外层，contains 判交集 通过判断可以判断是返回的长度
Set<Integer> smallSet;
Set<Integer> bigSet;
if (nums1Set.size() <= nums2Set.size()) {
smallSet = nums1Set;
bigSet = nums2Set;
} else {
smallSet = nums2Set;
bigSet = nums1Set;
}
// 计数
int returnLength = 0;
for (Integer v : smallSet) //时间复杂度为O(min(m, n))
{
if (bigSet.contains(v))
{
returnLength++;
}
}
// 分配并填充
int[] nums3 = new int[returnLength];
int returnIndex = 0;
for (Integer v : smallSet)// 时间复杂度为O(min(m, n))
{
if (bigSet.contains(v))
{
nums3[returnIndex++] = v;
}
}
return nums3;
}
}
则最终时间复杂度为Math.max(O(min(m, n)),O(m+n))即O(m+n)