349. Intersection of Two Arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1]
, nums2 = [2, 2]
, return [2]
.
Note: Each element in the result must be unique. The result can be in any order.
自己的解法
使用 set 进行去重
public static int[] intersection2(int[] nums1, int[] nums2) {
Set<Integer> nums1Set = new HashSet<>();
Set<Integer> set = new HashSet<>();
for (int integer : nums1) {
nums1Set.add(integer);
}
for (int integer : nums2) {
if (nums1Set.contains(integer)) {
set.add(integer);
}
}
int[] result = new int[set.size()];
int i = 0;
for (int integer : set) {
result[i] = integer;
i++;
}
return result;
}
别人的思路
LeetCode – Intersection of Two Arrays (Java)
Binary Search
public int[] intersection(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i=0; i<nums1.length; i++){
if(i==0 || (i>0 && nums1[i]!=nums1[i-1])){
if(Arrays.binarySearch(nums2, nums1[i])>-1){
list.add(nums1[i]);
}
}
}
int[] result = new int[list.size()];
int k=0;
for(int i: list){
result[k++] = i;
}
return result;
}
Time = O(nlog(n)). Space = O(n).