LeetCode 349：兩個數組的交集 Intersection of Two Arrays
- 2019 年 10 月 10 日
- 筆記
題目：
給定兩個數組，編寫一個函數來計算它們的交集。
Given two arrays, write a function to compute their intersection.
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2] 輸出: [2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 輸出: [9,4]
說明:
- 輸出結果中的每個元素一定是唯一的。
- 我們可以不考慮輸出結果的順序。
Note:
- Each element in the result must be unique.
- The result can be in any order.
解題思路：
三次遍歷通用解題：
- 第一次 nums1 加入 set1 ()集合，此時 set1() 內元素為去重後的 nums1 集合。
- 第二次 將 nums2 中的同時存在於 set1 的元素加入到 set 2() 集合，此時 set2() 集合即為兩個數組的交集。
- 第三次 將 set2() 集合中的元素提取出作為整型數組返回。
程式碼：
Java:
class Solution { public int[] intersection(int[] nums1, int[] nums2) { Set<Integer> set1 = new HashSet<>(); Set<Integer> set2 = new HashSet<>(); for (int num : nums1) //去重 set1.add(num); for (int num : nums2) { if (set1.contains(num)) set2.add(num); //依然用 set() 集合存交集元素以防止元素重複 } int[] res = new int[set2.size()]; int i = 0; for (int num : set2)//轉為 int[] res[i++] = num; return res; } }
Python：
在Py語言里有交集、並集、差集的概念：
A 與 B交集：A & B A 與 B並集：A | B A 與 B差集：A - B
所以一行程式碼即可解題：
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: # nums1、nums2轉為set集合併取交集，並將交集元素轉為list數組返回 return list(set(nums1) & set(nums2))
