349 Intersection of Two Arrays 兩個(gè)數(shù)組的交集
Description:
Given two arrays, write a function to compute their intersection.
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]
Note:
Each element in the result must be unique.
The result can be in any order.
題目描述:
給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來計(jì)算它們的交集华烟。
示例 :
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [9,4]
說明:
輸出結(jié)果中的每個(gè)元素一定是唯一的智什。
我們可以不考慮輸出結(jié)果的順序。
思路:
利用 set存儲不重復(fù)的值
- 先將 nums1全部存入 set, 循環(huán)判斷 set不在 nums2的全部移除
- 使用 2個(gè) set判斷, 交集加入 set
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(n)
代碼:
C++:
class Solution
{
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
set<int> set1(nums1.begin(), nums1.end()), set2(nums2.begin(), nums2.end());
vector<int> result;
/* set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result) 傳入兩個(gè)排序 set的首尾
* back_inserter(Iterator i) 使用 push_back()方法向 i中插入元素
*/
set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), back_inserter(result));
return result;
}
};
Java:
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Set<Integer> temp = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
temp.add(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
if (temp.contains(nums2[i])) set.add(nums2[i]);
}
int[] result = new int[set.size()];
Iterator iterator = set.iterator();
int i = 0;
while (iterator.hasNext()) {
result[i++] = (int)iterator.next();
}
return result;
}
}
Python:
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
