?LeetCode刷題實戰(zhàn)349：兩個數(shù)組的交集
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數(shù)組進行排序
Arrays.sort(nums1);
// 遍歷nums2的每個元素
for (int num2 : nums2) {
// 對比nums1中的元素
for (int num1 : nums1) {
// 相等保存到set中
if (num1 == num2) {
set.add(num1);
break;
}
// 如果num1已經(jīng)大于num2，說明這個數(shù)不是交集，跳出循環(huán)
if (num1 > num2) {
break;
}
}
}
// 轉(zhuǎn)成數(shù)組
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數(shù)組進行排序
Arrays.sort(nums1);
Set<Integer> set = new HashSet<>();
// 遍歷nums2數(shù)組
for (int target : nums2) {
// 每個元素都到nums1數(shù)組中二分查找
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;
}
}
}
// 轉(zhuǎn)成數(shù)組
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數(shù)組的所有元素放到set中
for (int num : nums1) {
set1.add(num);
}
// 遍歷nums2數(shù)組，如果nums2的元素存在于set1中，放入set2中
for (int num : nums2) {
if (set1.contains(num)) {
set2.add(num);
}
}
// 轉(zhuǎn)成數(shù)組
int[] ret = new int[set2.size()];
int i = 0;
for (int num : set2) {
ret[i++] = num;
}
return ret;
}
}