问题描述
解法
分析
Python 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
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 实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
|
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
近期评论