Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up: - What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
一刷
題解：這題很容易犯的錯(cuò)誤是晤硕，如果有[2,2]和[2], 如果隨機(jī)選一個(gè)作為binarysearch的參照，結(jié)果集會(huì)是[2,2]而不是正確的[2]蝙眶。
這回采用的方法是乐严，同時(shí)sort num1, num2,
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int len1 = nums1.length, len2 = nums2.length;
int i=0, j = 0;
List<Integer> res = new ArrayList<>();
while(i<len1 && j<len2){
if(nums1[i]<nums2[j]) i++;
else if(nums1[i]>nums2[j]) j++;
else{
res.add(nums1[i]);
i++;
j++;
}
}
int[] a = new int[res.size()];
for(i=0; i<res.size(); i++) a[i] = res.get(i);
return a;
}
}
二刷：
思路同一刷
public class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
List<Integer> res = new ArrayList<Integer>();
int i = 0, j = 0;
int len1 = nums1.length, len2 = nums2.length;
while(i<len1 && j<len2){
if(nums1[i] <nums2[j]) i++;
else if(nums1[i] > nums2[j]) j++;
else{
res.add(nums1[i]);
i++;
j++;
}
}
int[] a = new int[res.size()];
for(int in=0; in<res.size(); in++){
a[in] = res.get(in);
}
return a;
}
}
