[Leetcode]350. Intersection of Two Arrays II(C++)

题目描述

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

例子

例子 1

Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]

例子 2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]

Follow Up

What if the given array is already sorted? How would you optimize your algorithm? What if nums1’s size is small compared to nums2’s size? Which algorithm is better? What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Constraints

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 1000

解题思路

[Leetcode]349. Intersection of Two Arrays(C++) 的升级版，要求匹配两数组相同数量的元素，同样可以用二分查找来完成，由于需要匹配相同的数量的元素，所以在二分查找找到目标值之后需要左右扫描找到目标值元素的个数，有几个技巧可以提升速度。

左右扫描的找目标值元素的过程同样可以用二分查找来完成，参考：[Leetcode]34. Find First and Last Position of Element in Sorted Array(C++)
由于两数组都排序了，所以在每次二分查找结束之后都可以更新下一次查找的左边界（即当前目标值在数组中最后一个位置再加一）
其余更简单的方法有哈希表（空间换时间），双指针（也需要预先排序）等等

代码如下：

#include <algorithm>
#include <vector>

class Solution {
public:
    std::vector<int> intersect(std::vector<int>& nums1,
                               std::vector<int>& nums2) {
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());

        std::vector<int> result;

        int left = 0;
        int right = nums1.size() - 1;
        int count = 0;
        for (size_t i = 0; i < nums2.size(); ++i) {
            if (i > 0 && nums2[i] == nums2[i - 1]) {
                if (count > 0) {
                    result.push_back(nums2[i]);
                    count--;
                }
            } else {
                int target = nums2[i];
                count = binary_search(nums1, left, right, target);
                if (count > 0) {
                    result.push_back(nums2[i]);
                    count--;
                }
            }
        }

        return result;
    }

private:
    int binary_search(const std::vector<int>& nums, int& n_left, int n_right,
                      int target) {
        int left = n_left;
        int right = n_right;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                int count = 1;
                left = mid - 1;
                while (left >= n_left && nums[left] == target) {
                    left--;
                    count++;
                }
                n_left = mid + 1;
                while (n_left <= n_right && nums[n_left] == target) {
                    n_left++;
                    count++;
                }
                return count;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return 0;
    }
};

时间复杂度: O(nlog n) -> 排序时间
空间复杂度: O(1)

GitHub 代码同步地址： 350.IntersectionOfTwoArraysIi.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions