Leetcode #350 Intersection of Two Arrays II

[yokostan]

Binary Search:

class Solution {
    public List<Integer> list = new ArrayList<>();
    public int[] intersect(int[] nums1, int[] nums2) {

        if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
            return new int[0];
        }

        Arrays.sort(nums2);
        Arrays.sort(nums1);

        int lowerBound = 0;

        for (int i = 0; i < nums1.length; i++) {
            int index = intersection(nums1[i], nums2, lowerBound);
            if (index < nums2.length && nums1[i] == nums2[index]) {
                list.add(nums1[i]);
                lowerBound = index + 1;
            }
        }

        int i = 0;
        int[] res = new int[list.size()];
        for (int n : list) {
            res[i] = n;
            i++;
        }

        return res;
    }

    private int intersection(int target, int[] nums2, int lo) {
        int start = lo;
        int end = nums2.length - 1;

        while (start < end) {
            int mid = (end - start) / 2 + start;
            if (nums2[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return start;
    }
}

What an elegant solution to add a loweBound to the original binary search problem!, thus we should move the condition judging statements out to the main funciton. But still, elegant!

Two Pointers:

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int p1 = 0, p2 = 0, count = 0;
        int[] tmp = new int[Math.min(nums1.length, nums2.length)];

        while (p1 != nums1.length && p2 != nums2.length) {
            if (nums1[p1] == nums2[p2]) {
                tmp[count] = nums1[p1];
                count++;
                p1++;
                p2++;
            }
            else if (nums1[p1] < nums2[p2]) {
                p1++;
            }
            else p2++;
        }

        return Arrays.copyOf(tmp, count);
    }
}

HashMap:

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                map.put(nums1[i], map.get(nums1[i]) + 1);
            }
            else {
                map.put(nums1[i], 1);
            }
        }

        List<Integer> res = new ArrayList<>();

        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0) {
                res.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i]) - 1);
            }
        }

        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }

        return ans;
    }
}

The runtime: Two Pointers < Binary Search < HashMap