首页 > 代码库 > 350. Intersection of Two Arrays II

350. Intersection of Two Arrays II

2024-09-03 22:09:10   218人阅读

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

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

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?
    来源： https://leetcode.com/problems/intersection-of-two-arrays-ii/

分析

算法1

第一种方法，使用multiset，建立两个set，并且遍历较短的那个nums。这种方法适用于排序和未排序的数组
set的构造时间复杂度 N*log(N)
erase： log(N) + target.count 重复N次，所以erase总时间复杂度 N*log(N)
所以该算法时间复杂度为 N*log(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        multiset<int> set1(nums1.begin(), nums1.end());
        multiset<int> set2(nums2.begin(), nums2.end());
        vector<int> result;
        vector<int> & nums = nums1.size() > nums2.size() ? nums2 : nums1;// nums equals to the shorter array
        for(auto n : nums){
            int a = set1.erase(n);// find the count of n in nums1
            int b = set2.erase(n);// find the count of n in nums2
            if( a && b){
                int time = min(a,b);
                while(time--)
                    result.push_back(n);            
            }
        }
        return result;
    }
};

算法2

可以使用系统函数 set_intersection求解两个已经排序好的数组的交集
http://www.cplusplus.com/reference/algorithm/set_intersection/
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result(nums1.size() + nums2.size());
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        auto it = set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), result.begin());
        result.resize(it - result.begin());
        return result;
    }
};

可以自己实现 交集 功能
比如下面的两个排序好的数组，用两个指针分别指向开头，诶个遍历，直到有一个遍历结束

如果 A[i] < B[j]，i++
否则如果 B[j] < A[i]，j++
否则（这里一定是二者相等）push 当前值到 result，并且i++,j++

时间复杂度是O(N+M)

  i
A:1 1 2 3 3 4 4 4 4 5
  j-
B:0 0 1 1 2 2 4 4 6    result:
  i
A:1 1 2 3 3 4 4 4 4 5
    j-
B:0 0 1 1 2 2 4 4 6    result:
  i-
A:1 1 2 3 3 4 4 4 4 5
      j-
B:0 0 1 1 2 2 4 4 6    result:1
    i-
A:1 1 2 3 3 4 4 4 4 5
        j-
B:0 0 1 1 2 2 4 4 6    result:1,1
      i-
A:1 1 2 3 3 4 4 4 4 5
          j-
B:0 0 1 1 2 2 4 4 6    result:1,1,2
        i
A:1 1 2 3 3 4 4 4 4 5
            j-
B:0 0 1 1 2 2 4 4 6    result:1,1,2
        i-
A:1 1 2 3 3 4 4 4 4 5
              j
B:0 0 1 1 2 2 4 4 6    result:1,1,2
          i-
A:1 1 2 3 3 4 4 4 4 5
              j
B:0 0 1 1 2 2 4 4 6    result:1,1,2
            i-
A:1 1 2 3 3 4 4 4 4 5
              j-
B:0 0 1 1 2 2 4 4 6    result:1,1,2,4
              i-
A:1 1 2 3 3 4 4 4 4 5
                j-
B:0 0 1 1 2 2 4 4 6    result:1,1,2,4,4
                i-
A:1 1 2 3 3 4 4 4 4 5
                  j
B:0 0 1 1 2 2 4 4 6    result:1,1,2,4,4
                  i-
A:1 1 2 3 3 4 4 4 4 5
                  j
B:0 0 1 1 2 2 4 4 6    result:1,1,2,4,4
                    i-
A:1 1 2 3 3 4 4 4 4 5
                  j
B:0 0 1 1 2 2 4 4 6    result:1,1,2,4,4
                      i(end)
A:1 1 2 3 3 4 4 4 4 5
                  j
B:0 0 1 1 2 2 4 4 6    result:1,1,2,4,4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result(nums1.size() + nums2.size());
        int i = 0;
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        auto l1 = nums1.begin(), r1 = nums1.end();
        auto l2 = nums2.begin(), r2 = nums2.end();
        while(l1 < r1 && l2 < r2){
            if(*l1 < *l2){
                ++l1;
            }
            else if(*l1 > *l2){
                ++l2;
            }
            else{
                result[i++] = *l1;
                ++l1; ++l2;
            }
        }
        result.resize(i);
        return result;
    }
};

算法3

如果只有nums1可以装进内存，那么可以将nums1放入一个 Hash Table 中，然后读取部分 nums2 到内存，逐个判断并压入result中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mymap;
        vector<int> result;
        for(auto n: nums1){
            ++mymap[n];
        }
        for(auto n: nums2){
            if(mymap[n]-- > 0){
                result.push_back(n);
            }
        }
        return result;
    }
};
如果nums1和nums2都不能够一次性放在内存中，那么首先对二者进行外部排序，external sort，然后每次读取一部分数据进来，进行算法2，然后不断读取数据



null


350. Intersection of Two Arrays II


联系
我们