349. Intersection of Two Arrays

find intersection, use set, this one is better

time: O(n)

space: O(n)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // first instinction, use hashset, add data, find duplicate, add to array
        Set<Integer> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();

        for (int num : nums1) {
            set.add(num);
        }
        for (int num : nums2) {
            if (set.contains(num)) {
                list.add(num);
                set.remove(num);
            }
        }
        return list.stream().mapToInt(n -> n).toArray();
    }
}

sort first, then use binary search, find and add into set, this is another thought, but time complexity is not good.

time: O(nlogn)

space: O(n)

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> res = new HashSet<>();
        Arrays.sort(nums1);
        for (int num : nums2) {
            if (bs(nums1, num)) {
                res.add(num);
            }
        }
        int[] result = new int[res.size()];
        int i = 0;
        for (int num : res) {
            result[i++] = num;
        }
        return result;
    }
    private boolean bs(int[] nums, int num) {
        int start = 0;
        int end = nums.length-1;
        while (start + 1 < end) {
            int mid = start + (end - start)/2;
            if (nums[mid] < num) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] == num) {
            return true;
        }
        if (nums[end] == num) {
            return true;
        }
        return false;
    }
}

JS

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const set = new Set(nums1);
    
    return [...new Set(nums2.filter(n => set.has(n)))];
};