leetcode. 349. intersection of two arrays

349. Intersection of two arrays
     Given two arrays nums1 and nums2 , return Their intersection . Every element in the output must be only Of . We can Regardless of the order of the output results .

Example 1：

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

Example 2：

Input ：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output ：[9,4]
explain ：[4,9] It is also passable

Method 1 ： about python You can use set Fast implementation of properties and functions of

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cur1 = set(nums1)
        cur2 = set(nums2)
        return list(cur1&cur2)

Method 2 ：
C++ Realization , You can use map Judge

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> m;
        vector<int> res;
        for (auto it : nums1){
            m[it]++;
        }
        for (auto it: nums2){
            if (m[it]!=0){
                res.emplace_back(it);
                m[it]=0;
            }
        }
        return res;
    }
};

• Time complexity ：O(n)
• Spatial complexity ：O(n)

Method 3 ： Sort + Double pointer ( have no thoughts of , Summarized in the solution )
If two arrays are ordered , You can use the double pointer method to get the intersection of two arrays .

First, sort the two arrays , Then use two pointers to traverse the two arrays . Predictably, the elements added to the array of answers must be incremented , In order to ensure the uniqueness of the added elements , We need to record additional variables pre Represents the last element added to the answer array .

At the beginning , The two pointers point to the heads of the two arrays . Compare the numbers in the two arrays pointed to by two pointers at a time , If the two numbers are not equal , Moves the pointer to the smaller number one bit to the right , If two numbers are equal , And the number is not equal to pre , Add this number to the answer and update pre Variable , Move both pointers to the right one bit at the same time . When at least one pointer is out of the range of the array , End of traversal .

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int length1 = nums1.size(), length2 = nums2.size();
        int index1 = 0, index2 = 0;
        vector<int> intersection;
        while (index1 < length1 && index2 < length2) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                //  Ensure the uniqueness of the added elements 
                if (!intersection.size() || num1 != intersection.back()) {
                    intersection.push_back(num1);
                }
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return intersection;
    }
};

• Time complexity ：$O(m\log m+n\log n)$, among m and n Are the lengths of the two arrays . The time complexity of sorting the two arrays is $O(m\log m)$ and $O(n\log n)$, The time complexity of finding intersection elements with double pointers is $O(m+n)$, So the total time complexity is $O(m\log m+n\log n)$.

• Spatial complexity ：$O(\log m+\log n)$, among m and n Are the lengths of the two arrays . The space complexity mainly depends on the additional space used by sorting .