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.

一刷
题解：就是找两个数组中重复的元素，并加入到结果集中。并且结果集中元素不重复。

方法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;
    }
}