🔗 🟢 2956. Find Common Elements Between Two Arrays 1215

tags: Biweekly Contest 119 陣列(Array) 雜湊表(Hash Table)

題意

給定 nums1nums1 和 nums2nums2 兩個陣列，分別有 nn 和 mm 個元素。

  • 統計 0≤i<n0 \leq i < n 且 nums1[i]nums1[i] 在 nums2nums2 中至少出現一次的元素個數。
  • 統計 0≤i<m0 \leq i < m 且 nums2[i]nums2[i] 在 nums1nums1 中至少出現一次的元素個數。

返回一個長度為 22 的整數陣列 answeranswer，分別為以上兩個數值。

思路：雜湊集合(Hash Set)

由於我們考慮的是至少出現一次，因此只需要考慮有出現或沒有出現兩種情況即可。先使用兩個 Hash Set 來分別記錄 nums1nums1 和 nums2nums2 中出現的元素，再分別計算 nums1nums1 和 nums2nums2 中的每個元素在另一個陣列中有無出現即可。

複雜度分析

  • 時間複雜度：O(n+m)\mathcal{O}(n + m)，其中 nn 是 nums1nums1 的長度，mm 是 nums2nums2 的長度。
    • 建立集合的時間複雜度是 O(n+m)\mathcal{O}(n + m)。
    • 遍歷兩個陣列並進行查找的時間複雜度也是 O(n+m)\mathcal{O}(n + m)。
  • 空間複雜度：O(n+m)\mathcal{O}(n + m)，需要額外空間來存儲兩個集合。
1
2
3
4
5
6
7
class Solution:
    def findIntersectionValues(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        ans1 = sum([1 for x in nums1 if x in set2])
        ans2 = sum([1 for x in nums2 if x in set1])
        return [ans1, ans2]
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> findIntersectionValues(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> set1(nums1.begin(), nums1.end()), set2(nums2.begin(), nums2.end());
        vector<int> ans(2);
        for (int x : nums1) ans[0] += set2.count(x);
        for (int x : nums2) ans[1] += set1.count(x);
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality,extremely detailed CG unity 8k wallpaper, HDR, High Detail,
1girl, solo, long hair, bangs, brown hair, shirt, long sleeves, dress, white shirt, outdoors, day, white dress, blurry, from side, tree, lips, looking up, building, photo background