LeetCode刷题实战349:两个数组的交集
共 7802字,需浏览 16分钟
·
2021-08-11 13:57
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.
示例
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
解题
解法一:set
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// set
Set<Integer> set = new HashSet<>();
// 对nums1数组进行排序
Arrays.sort(nums1);
// 遍历nums2的每个元素
for (int num2 : nums2) {
// 对比nums1中的元素
for (int num1 : nums1) {
// 相等保存到set中
if (num1 == num2) {
set.add(num1);
break;
}
// 如果num1已经大于num2,说明这个数不是交集,跳出循环
if (num1 > num2) {
break;
}
}
}
// 转成数组
int[] ret = new int[set.size()];
int i = 0;
for (int num : set) {
ret[i++] = num;
}
return ret;
}
}
解法二:二分查找法
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// 二分查找
// 对nums1数组进行排序
Arrays.sort(nums1);
Set<Integer> set = new HashSet<>();
// 遍历nums2数组
for (int target : nums2) {
// 每个元素都到nums1数组中二分查找
int l = 0, r = nums1.length - 1;
while (l <= r) {
// 取中位下标
int mid = l + (r - l) / 2;
if (target < nums1[mid]) {
r = mid - 1;
} else if (target > nums1[mid]) {
l = mid + 1;
} else {
// 相等,保存到set中
set.add(target);
break;
}
}
}
// 转成数组
int[] ret = new int[set.size()];
int i = 0;
for (int num : set) {
ret[i++] = num;
}
return ret;
}
}
解法三:双set
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
// 双set
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>(); // 存放交集元素
// 先把nums1数组的所有元素放到set中
for (int num : nums1) {
set1.add(num);
}
// 遍历nums2数组,如果nums2的元素存在于set1中,放入set2中
for (int num : nums2) {
if (set1.contains(num)) {
set2.add(num);
}
}
// 转成数组
int[] ret = new int[set2.size()];
int i = 0;
for (int num : set2) {
ret[i++] = num;
}
return ret;
}
}