350.两个数组的交集

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
// 哈希表，记录数字出现的次数
var intersect = function (nums1, nums2) {
    var map = {}
    var res = []
    for (var i = 0; i < nums1.length; i++) {
        if (map[nums1[i]]) {
            map[nums1[i]]++
        } else {
            map[nums1[i]] = 1
        }
    }
    for (var i = 0; i < nums2.length; i++) {
        if (map[nums2[i]] && map[nums2[i]] > 0) {
            res.push(nums2[i])
            map[nums2[i]]--
        }
    }
    return res
};

// 排序+双指针
var intersect = function (nums1, nums2) {
    // 先对数组排序
    nums1.sort((a, b) => a - b)
    nums2.sort((a, b) => a - b)
    // 定义两个指针，每次取出两个数比较，如果相同则插入结果，如果不同则把数值小的指针向前移动一格
    var p1 = 0
    var p2 = 0
    var res = []
    while (p1 < nums1.length && p2 < nums2.length) {
        var n1 = nums1[p1]
        var n2 = nums2[p2]
        if (n1 === n2) {
            res.push(n1)
            p1++
            p2++
            continue
        }

        if (n1 > n2) {
            p2++
        } else {
            p1++
        }
    }

    return res
};

// 排序+二分查找
var intersect = function (nums1, nums2) {
    var res = []
    // 先对nums1数组排序
    nums1.sort((a, b) => a - b)
    // 每次从nums2取出一个数到nums1查找
    nums2.forEach(val => {
        var left = 0
        var right = nums1.length - 1
        while (left <= right) {
            var mid = parseInt((left + right) / 2)
            if (nums1[mid] === val) {
                res.push(val)
                // 将这个数从nums1中删除
                nums1.splice(mid, 1)
                break
            } else if (nums1[mid] > val) {
                right = mid - 1
            } else if (nums1[mid] < val) {
                left = mid + 1
            }
        }
    })

    return res
};


// 示例 1：
// 输入：nums1 = [1,2,2,1], nums2 = [2,2]
// 输出：[2,2]
console.log(intersect([1, 2, 2, 1], [2, 2]))


// 示例 2:
// 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
// 输出：[4,9]
console.log(intersect([4, 9, 5], [9, 4, 9, 8, 4]))