349. Intersection of Two Arrays
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]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
3. Note
- Each element in the result must be unique.
- The result can be in any order.
4. Solutions
My Accepted Solution
n = max(i_nums1.size(), i_nums2.size())
Time complexity: O($nlog_2n$)
Space complexity: O(n)
class Solution
{
public:
// vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
vector<int> intersection(vector<int>& i_nums1, vector<int>& i_nums2)
{
sort(i_nums1.begin(), i_nums1.end());
sort(i_nums2.begin(), i_nums2.end());
unordered_set<int> resultSet;
for(int i = 0, j = 0; i < i_nums1.size() && j < i_nums2.size(); )
{
if(i_nums1[i] == i_nums2[j])
{
resultSet.insert(i_nums1[i]);
i++;
j++;
}
else
{
i_nums1[i] < i_nums2[j] ? i++ : j++;
}
}
vector<int> result;
result.insert(result.end(), resultSet.begin(), resultSet.end());
return result;
}
};
4.1 Optimized Version
n = max(i_nums1.size(), i_nums2.size())
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
// vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
vector<int> intersection(const vector<int> &i_nums1, const vector<int> &i_nums2)
{
if(i_nums1.empty() || i_nums2.empty()) return vector<int>{};
unordered_set<int> uniqueValueNums1(i_nums1.begin(), i_nums1.end());
vector<int> result(min(i_nums1.size(), i_nums2.size()));
int iter = 0;
for(auto num : i_nums2)
{
if(uniqueValueNums1.erase(num) > 0)
{
result[iter] = num;
iter++;
}
}
result.erase(result.begin()+iter, result.end());
return result;
}
};