首页 > itarticle > 算法笔记: 力扣#350 两个数组的交集 ii

算法笔记: 力扣#350 两个数组的交集 ii

admin 11月 12, 2020 0

问题描述

解法

分析

Python 实现

class :
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        counter = dict()
        ans = []
        for num in nums1:
            counter[num] = counter.get(num, 0) + 1
        for num in nums2:
            if counter.get(num, 0):
                ans.append(num)
                counter[num] -= 1
        return ans

Java 实现

class  {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> counter = new HashMap<>();
        List<Integer> res = new ArrayList<>();
        for(int num : nums1){
            counter.put(num, counter.getOrDefault(num, 0)+1);
        }
        for(int num : nums2){
            if(counter.getOrDefault(num,0)>0){
                res.add(num);
                counter.put(num, counter.get(num)-1);
            }
        }
        int[] ans = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
}

时间复杂度

O(n)

空间复杂度

O(n)

链接

350. Intersection of Two Arrays II
350. 两个数组的交集 II
(English version) Algorithm Notes: Leetcode#350 Intersection of Two Arrays 2