class Solution {
/**
1.要求返回一个整型，元素不重复数组，可以利用集合set的特性
2.先将一个nums1值保存在set1中，循环nums2，判断set1中是否存在nums2中的值，存在则保存在set2中
3.将set2转换为int[]
>先将set2转为Integer型数组
>再将Integer型数组转为int型数组
**/
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet();
Set<Integer> set2 = new HashSet();
for (int a : nums1) {
set1.add(a);
}
for (int b : nums2) {
if (set1.contains(b)) {
set2.add(b);
}
}
Integer[] temp = set2.toArray(new Integer[] {});
int[] intArray = new int[temp.length];
for (int i = 0; i < temp.length; i++) {
intArray[i] = temp[i].intValue();
}
return intArray;
}
}
官方解题思路：
方法1：Set（题解中出现最多的）
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
return new int[0];
}
Set<Integer> parentSet = new HashSet<>();
Set<Integer> childSet = new HashSet<>();
for (int num : nums1) {
parentSet.add(num);
}
for (int num : nums2) {
if (parentSet.contains(num)) {
childSet.add(num);
}
}
int[] resArr = new int[childSet.size()];
int index = 0;
for (int value : childSet) {
resArr[index++] = value;
}
return resArr;
}
方法2：双指针
先将nums1 与nums2排序，然后游走两个指针，情况都写出来了，没有用else
时间复杂度：O(nlogn)
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0, j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
set.add(nums1[i]);
i++;
j++;
} else if (nums1[i] < nums2[j]) {
i++;
} else if (nums1[i] > nums2[j]) {
j++;
}
}
int[] res = new int[set.size()];
int index = 0;
for (int num : set) {
res[index++] = num;
}
return res;
}
方法3：二分查找
将nums2排序，然后查找nums2的元素，需要准备一个binarySearch的辅助方法，注意left<= right
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums2);
for (int target : nums1) {
if (binarySearch(nums2, target) && !set.contains(target)) {
set.add(target);
}
}
int index = 0;
int[] res = new int[set.size()];
for (int num : set) {
res[index++] = num;
}
return res;
}
public boolean binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
return false;
}
