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.
一刷
题解：就是找两个数组中重复的元素，并加入到结果集中。并且结果集中元素不重复。
方法1: 用2个set很简单。nums1一个，结果集一个。
方法2: BinarySearch
将nums1 sort, 对于num2中的每个元素，利用BinarySearch判断是否存在，存在则加入set中
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Arrays.sort(nums2);
for(int num : nums1){
if(bs(nums2, num)) set.add(num);
}
int[] res = new int[set.size()];
int i = 0;
for(int num : set){
res[i] = num;
i++;
}
return res;
}
private boolean bs(int[] nums, int target){
int lo = 0, hi = nums.length-1;
while(lo<=hi){
int mid = lo + (hi - lo)/2;
if(nums[mid] == target) return true;
else if(nums[mid]<target) lo = mid+1;
else hi = mid-1;
}
return false;
}
}
