350. Intersection of Two Arrays II
1. Description
Given two arrays, write a function to compute their intersection.
2. Example
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
3. Note
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
4. 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?
5. Solutions
My Accepted Solution
Follow Up 1: use my solution, so we don’t need to sort, time complexity coule be O(m+n) Follow Up 2: turn the small array into the hashtable Follow Up 3: if one array is small, then we could put it into the memory, and split the other array and put them into the memory one by one. if both arrays are big, we could use external sort, and use my solution, two pointers
m = m_nums1.size(), n = m_nums2.size()
Time complexity: O($mlog_2m + nlog_2n$)
Space complexity: O(min(m, n))
class Solution
{
public:
// vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
vector<int> intersect(vector<int> &m_nums1, vector<int> &m_nums2)
{
sort(m_nums1.begin(), m_nums1.end());
sort(m_nums2.begin(), m_nums2.end());
vector<int> result;
for(int i = 0, j = 0; i < m_nums1.size() && j < m_nums2.size(); )
{
if(m_nums1[i] == m_nums2[j])
{
result.push_back(m_nums1[i]);
i++;
j++;
}
else if(m_nums1[i] < m_nums2[j]) i++;
else if(m_nums1[i] > m_nums2[j]) j++;
}
return result;
}
};
5.1 Hash Table
m = m_nums1.size(), n = m_nums2.size()
Time complexity: O(m + n)
Space complexity: O(min(m, n))
class Solution
{
public:
// vector<int> intersect(vector<int>& nums1, vector<int>& nums2)
vector<int> intersect(vector<int> &m_nums1, vector<int> &m_nums2)
{
if(m_nums1.size() > m_nums2.size()) swap(m_nums1, m_nums2);
map<int, int> numberTimes;
for(int i = 0; i < m_nums1.size(); i++)
numberTimes[m_nums1[i]]++;
vector<int> result;
for(int i = 0; i < m_nums2.size(); i++)
{
if(numberTimes[m_nums2[i]] > 0)
{
result.push_back(m_nums2[i]);
numberTimes[m_nums2[i]]--;
}
}
return result;
}
};