示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2]
示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4] 解释:[4,9] 也是可通过的
方法一:两个集合 计算两个数组的交集,直观的方法是遍历数组nums1 ,对于其中的每个元素,遍历数组nums2判断该元素是否在数组nums2中,如果存在,则将该元素添加到返回值。假设数组nums1和nums2的长度分别是m和n,则遍历数组nums1需要O(m)的时间,判断nums1中的每个元素是否在数组nums2中需要O(n)的时间,因此总时间复杂度是O(mn)。如果使用哈希集合存储元素,则可以在O(1)的时间内判断一个元素是否在集合中,从而降低时间复杂度。 首先使用两个集合分别存储两个数组中的元素,然后遍历较小的集合,判断其中的每个元素是否在另一个集合中,如果元素也在另一个集合中,则将该元素添加到返回值。该方法的时间复杂度可以降低到o(m + n)。 复杂度分析 · 时间复杂度:O(m + n),其中m和n分别是两个数组的长度。使用两个集合分别存储两个数组中的元素需要o(m + n)的时间,遍历较小的集合并判断元素是否在另—个集合中需要O(min(m,rn))的时间,因此总时间复杂度是o(m + n)。 · 空间复杂度:O(m +n),其中 m和n分别是两个数组的长度。空间复杂度主要取决于两个集合。
方法二:排序+双指针 如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。 首先对两个数组进行排序,然后使用两个指针遍历两个数组。可以预见的是加入答案的数组的元素一定是递增的,为了保证加入元素的唯一性,我们需要额外记录变量pre表示上一次加入答案数组的元素。 初始时,两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字,如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,且该数字不等于pre,将该数字添加到答案并更新 pre变量,同时将两个指针都右移一位。当至少有一个指针超出数组范围时,遍历结束。 复杂度分析
方法一:两个集合
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
set2.add(num);
}
return getIntersection(set1, set2);
}
public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
if (set1.size() > set2.size()) {
return getIntersection(set2, set1);
}
Set<Integer> intersectionSet = new HashSet<Integer>();
for (int num : set1) {
if (set2.contains(num)) {
intersectionSet.add(num);
}
}
int[] intersection = new int[intersectionSet.size()];
int index = 0;
for (int num : intersectionSet) {
intersection[index++] = num;
}
return intersection;
}
}
方法二:排序 + 双指针
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[length1 + length2];
int index = 0, index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
int num1 = nums1[index1], num2 = nums2[index2];
if (num1 == num2) {
// 保证加入元素的唯一性
if (index == 0 || num1 != intersection[index - 1]) {
intersection[index++] = num1;
}
index1++;
index2++;
} else if (num1 < num2) {
index1++;
} else {
index2++;
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}