Problem:
Given two arrays, write a function to compute their intersection.
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]
Note:
- Each element in the result must be unique.
- The result can be in any order.
思路:
Solution (C++):
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> s;
vector<int> res{};
int m = nums1.size(), n = nums2.size();
if (m == 0 || n == 0) return res;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
if (m <= n) {
for (int i = 0; i < m; ++i)
if (binarySearch(nums2, nums1[i])) s.insert(nums1[i]);
}
else {
for (int i = 0; i < n; ++i) {
if (binarySearch(nums1, nums2[i])) s.insert(nums2[i]);
}
}
for (auto x : s) res.push_back(x);
return res;
}
bool binarySearch(vector<int>& v, int num) {
int l = 0, r = v.size()-1, mid;
while (l <= r) {
mid = l + (r-l) / 2;
if (num == v[mid]) return true;
else if (num < v[mid]) r = mid - 1;
else l = mid + 1;
}
return false;
}
性能:
Runtime: 8 ms Memory Usage: 6.9 MB
思路:
Solution (C++):
性能:
Runtime: ms Memory Usage: MB
原文链接: https://www.cnblogs.com/dysjtu1995/p/12609310.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/339026
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!