首页 > itarticle > algorithm notes: leetcode#350 intersection of two arrays 2

algorithm notes: leetcode#350 intersection of two arrays 2

admin 11月 12, 2020 0

Problem

Solution

Analysis

Python implementation

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 implementation

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;
    }
}

Time complexity

O(n)

Space complexity

O(n)

Link

350. Intersection of Two Arrays II
(中文版) 算法笔记: 力扣#350 两个数组的交集 II