两个数组的交集II

来自力扣第350题两个数组的交集II

给定两个数组，编写一个函数来计算它们的交集。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

哈希map

常规写法，用一个map存储两个数组中较短数组的元素，以及次数，接着遍历第二个数组，判断第二个数组里的元素是否存在于map里。

public int[] intersect(int[] nums1, int[] nums2) {
    if(nums1.length > nums2.length)
        return intersect(nums2,nums1);
    HashMap<Integer,Integer> map = new HashMap<>();
    for (int value : nums1) {
        map.put(value, map.getOrDefault(value, 0) + 1);
    }
    List<Integer> ans = new ArrayList<>();
    for(int value : nums2){
       int a = map.getOrDefault(value,0);
        if(a > 0){
            ans.add(value);
            map.put(value,a-1);
        }
    }
    int[] res = new int[ans.size()];
    for(int i = 0 ; i < ans.size() ; i++)
        res[i] = ans.get(i);
    return res;
}

双指针

太久没写题了，都忘记还有排序后双指针的做法。

public int[] intersect(int[] nums1, int[] nums2) {
    // 排好序的写法
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    // 定义i，j两个指针，k用于记录交集的索引值
    int i = 0, j = 0, k = 0;
    while (i < nums1.length && j < nums2.length) {
        if(nums1[i] < nums2[j]) {
            // 说明num1[i]较小，i右移
            i++;
        } else if (nums1[i] > nums2[j]) {
            // 说明nums2[j]较小，j右移
            j++;
        } else {
            // 两个元素相同，记录在k
            nums1[k++] = nums1[i];
            // 两个指针向前走一步
            i++;
            j++;
        }
    }
    return Arrays.copyOfRange(nums1, 0, k);
}

另类哈希

找执行用时范例里看到的，本质上也是一种hash，只不过事先预设或找出测试用例里最大的元素值，那么这样对其求余即可，用数组作为哈希表，提升了运行时间。

private final int MAGIC = 1000;
public int[] intersect(int[] nums1, int[] nums2) {
    int j = 0;
    int freq[] = new int[MAGIC];
    for (int i = 0; i < nums1.length; i++) {
        freq[Math.abs(nums1[i] % MAGIC)]++;
    }
    
    int res[] = new int[nums1.length];
    for (int i = 0; i < nums2.length; i++) {
        if (freq[Math.abs(nums2[i] % MAGIC)]-- > 0) {
           res[j++] = nums2[i];
        }
    }
    return Arrays.copyOf(res, j);
}