[LintCode] 547 Intersection of Two Arrays 解题报告

Description
Given two arrays, write a function to compute their intersection.


Notice
Each element in the result must be unique.
The result can be in any order.



Example
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].



Challenge
Can you implement it in three different algorithms?



思路
这题有多种做法。
解法一
把一个数组排序。开一个空的hash表。遍历第二个数组的每一个元素，在第一个数组里二分查找有没有这个元素。如果有，就放到hash表里。
最后，hash表里的就是两个数组的intersection了。



Code

public class Solution {
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        // Write your code here
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[] {};
        }
    
        Arrays.sort(nums1);
        
        HashSet<Integer> hash = new HashSet<>();
        for (int num : nums2) {
            if (contains(nums1, num)) {
                hash.add(num);
            }
        }
        
        int[] res = new int[hash.size()];
        int i = 0;
        for (int num : hash) {
            res[i++] = num;
        }
        
        return res;
    }
    
    public boolean contains(int[] num, int target) {
        int start = 0;
        int end = num.length - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (num[mid] == target) {
                return true;
            }
            else if (num[mid] > target) {
                end = mid;
            }
            else {
                start = mid;
            }
        }
        
        return num[start] == target || num[end] == target;
    }
}