Leetcode - 349 Intersection of Two Arrays
Description
Given two arrays, write a function to compute their intersection.
Each element in the result must be unique.The order of the results needs to be ascending
Example
Example 1:
Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2],
Output: [2].
Example 2:
Input: nums1 = [1, 2], nums2 = [2],
Output: [2].
Solution1 -使用Hashset
时间复杂度 O(m)，空间复杂度 O(m) + O(n∩m)。
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i])){
set.remove(nums2[i]);
res.add(nums2[i]);
}
}
// Convert ArrayList to array
int[] arr = new int[res.size()];
for (int i = 0; i < res.size(); i++)
arr[i] = res.get(i);
return arr;
}
Solution2 - 使用最少辅助空间 O(n∩m)
时间复杂度 O(mlogm) + O(nlogn)，空间复杂度 O(n∩m) 。
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null)
return null;
if (nums1.length == 0 || nums2.length == 0)
return new int[0];
//sort - O(nlogn)
Arrays.sort(nums1);
//sort - O(mlogm)
Arrays.sort(nums2);
//removeDuplicate
int endIndex1 = removeDuplicate(nums1);
int endIndex2 = removeDuplicate(nums2);
LinkedList<Integer> list = new LinkedList<>();
int i = 0, j = 0;
while (i <= endIndex1 && j <= endIndex2) {
if (nums1[i] == nums2[j]) {
list.add(nums1[i]);
i++;
j++;
} else if (nums1[i] < nums2[j])
i++;
else if (nums1[i] > nums2[j])
j++;
}
int[] res = new int[list.size()];
i = 0;
for (int e : list) {
res[i] = e;
i++;
}
return res;
}
private int removeDuplicate(int[] arr) {
int index = 0;
int i = 0;
while (i < arr.length) {
if (arr[i] != arr[index]) {
index++;
arr[index] = arr[i];
}
i++;
}
return index;
}