今日算法之_110_两个数组的交集
前言
Github:https://github.com/HealerJean
1、两个数组的交集1
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
1.1、解题思路
集合解决
1.2、算法
public int[] intersection(int[] nums1, int[] nums2) {
List<Integer> list = Arrays.stream(nums1).mapToObj(Integer::new).collect(Collectors.toList());
Set<Integer> set = new HashSet<>();
for (int num : nums2) {
if (list.contains(num)) {
set.add(num);
}
}
return set.stream().mapToInt(Integer::intValue).toArray();
}
1.3、测试
@Test
public void test() {
int[] nums1 = {4, 9, 5};
int[] nums2 = {9, 4, 9, 8, 4};
System.out.println(Arrays.toString(intersection(nums1, nums2)));
}
2、两个数组的交集2
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
2.1、解题思路
1、集合
2、先排序,再移动指针
2.2、算法
2.2.1、算法1
/**
* list解决
*/
public int[] intersect1(int[] nums1, int[] nums2) {
List<Integer> list = Arrays.stream(nums1).mapToObj(Integer::new).collect(Collectors.toList());
List<Integer> resList = new ArrayList<>();
for (int num : nums2){
if (list.contains(num)){
list.remove((Integer)num);
resList.add(num);
}
}
return resList.stream().mapToInt(Integer::intValue).toArray();
}
2.2.2、算法2
/**
* 排序,移动指针,有点像合并有序数组
*/
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0 , j = 0 ;
int count = 0 ;
int[] res = new int[nums1.length + nums1.length];
while (i < nums1.length && j < nums2.length){
if (nums1[i] == nums2[j]){
res[count] = nums1[i];
i++ ;
j++ ;
count++;
}else if (nums1[i] < nums2[j]){
i++;
}else {
j++;
}
}
return Arrays.copyOfRange(res, 0, count);
}
2.3、测试
@Test
public void test() {
int[] nums1 = {4};
int[] nums2 = {9};
System.out.println(Arrays.toString( intersect(nums1, nums2)));
}