Topic describes

Given two arrays, write a function to calculate their intersection.

Example 1:
Enter: nums1 = [1.2.2.1], nums2 = [2.2] output: [2]
Copy the code
Example 2:
Enter: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [9.4]
Copy the code
Description:

Each element in the output must be unique. We can ignore the order of the output.

answer

First, nums1 is traversed, and the traversal results are stored in the map. Then nums2 is traversed. If numS2 elements appear in the map, they are stored, and the intersection of two arrays can be obtained.

function intersection(nums1, nums2) {
    const map = new Map(a)// Nums1 traversal is stored in a map, which makes lookup much faster
    for (const num of nums1) {
        map.set(num, true)}let k = 0;
    for (const num of nums2) {
        const value = map.get(num)
        if (value) {
            nums2[k] = num
            k++
            map.set(num, false)}}return nums2.slice(0, k)
}
Copy the code

variant

Given two arrays, write a function to calculate their intersection.

Example 1:
Enter: nums1 = [1.2.2.1], nums2 = [2.2] output: [2.2]
Copy the code
Example 2:
Enter: nums1 = [4.9.5], nums2 = [9.4.9.8.4] output: [4.9]
Copy the code
Description:

The number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays. We can ignore the order of the output.

Variant solutions

This problem is very similar to the previous one, except that the repeated data needs to be displayed repeatedly. In this way, when we store the map, we cannot simply express true, we need to count, and other steps are the same.

function intersection(nums1, nums2) {
    const map = new Map(a)for (const num of nums1) {
        const value = map.get(num) || 0
        map.set(num, value + 1)}let k = 0;
    for (const num of nums2) {
        const value = map.get(num)
        if (value > 0) {
            nums2[k] = num
            k++
            map.set(num, value - 1)}}return nums2.slice(0, k)
}
Copy the code

The advanced

Given two ordered arrays, write a function to calculate their intersection.

Example:
Input: sort array nums1 = [1.2.3.4.5], nums2 = [3.4.6.7] output: [3.4]
Copy the code

Advanced solutions

We can solve this problem by using double Pointers, moving index1 and index2 over and over, comparing the corresponding elements

function intersection(nums1, nums2) {
    let index1 = 0
    let index2 = 0

    const intersection = []
    while(index1 < nums1.length && index2 < nums2.length) {
        if (nums1[index1] === nums2[index2]) {
            Intersection is inserted when the two are equal when the element is empty, or when the element is not equal to the last element
            if(! intersection.length || nums1[index1] ! == intersection[intersection.length -1]) {
                intersection.push(nums1[index1])
                index1++
                index2++
            }
        } else if (nums1[index1] > nums2[index2]) {
            // nums1[index1] > nums2[index2], index2++
            index2++
        } else {
            index1++
        }
    }
    return intersection
}
Copy the code