首页 > 代码库 > LeetCode 349 Intersection of Two Arrays
LeetCode 349 Intersection of Two Arrays
Problem:
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1]
, nums2 = [2, 2]
, return [2]
.
- Each element in the result must be unique.
- The result can be in any order.
Summary:
求两集合交集。
Analysis:
1. 直接用了std中的find,遍历其中一个集合,查找其中的每个元素在另一个集合中是否存在。
1 class Solution { 2 public: 3 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { 4 vector<int> res; 5 int len1 = nums1.size(), len2 = nums2.size(); 6 7 for (int i = 0; i < len1; i++) { 8 if (find(nums2.begin(), nums2.end(), nums1[i]) != nums2.end() && 9 find(res.begin(), res.end(), nums1[i]) == res.end()) { 10 res.push_back(nums1[i]); 11 } 12 } 13 14 return res; 15 } 16 };
2. sort + merge
首先将两个数组从小到大排序,后分别用两个指针指向两个数组开头比较大小,将小的数组指针后移。直至两指针指向数字相等时考虑将数字放入res中。
注意此处应考虑res中是否包含该数字。
1 class Solution { 2 public: 3 vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { 4 vector<int> res; 5 int len1 = nums1.size(), len2 = nums2.size(); 6 7 sort(nums1.begin(), nums1.end()); 8 sort(nums2.begin(), nums2.end()); 9 10 int i = 0, j = 0; 11 while (i < len1 && j < len2) { 12 if (nums1[i] < nums2[j]) { 13 i++; 14 } 15 else if (nums1[i] > nums2[j]) { 16 j++; 17 } 18 else { 19 if (res.empty() || res.back() != nums1[i]) { 20 res.push_back(nums1[i]); 21 } 22 23 i++; 24 j++; 25 } 26 } 27 28 return res; 29 } 30 };
LeetCode 349 Intersection of Two Arrays
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。