目录
【LeetCode题解】350_两个数组的交集Ⅱ
描述
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]
说明：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
方法一：映射
Java 实现
import java.util.Map;import java.util.HashMap;import java.util.List;import java.util.ArrayList;class Solution { public int[] intersect(int[] nums1, int[] nums2) { if (nums1.length <= 0 || nums2.length <= 0) { return new int[] {}; } Map map = new HashMap<>(); for (int num : nums1) { if (map.containsKey(num)) { map.replace(num, map.get(num) + 1); } else { map.put(num, 1); } } List list = new ArrayList<>(); for (int num : nums2) { if (map.containsKey(num) && map.get(num) > 0) { list.add(num); map.replace(num, map.get(num) - 1); } } int[] ret = new int[list.size()]; for (int i = 0; i < list.size(); ++i) { ret[i] = list.get(i); } return ret; }}// Runtime: 6 ms// Your runtime beats 34.15 % of java submissions. 复杂度分析：
- 时间复杂度：\(O(n)\)
- 空间复杂度：\(O(n)\)
Python 实现
class Solution: def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ if len(nums1) == 0 or len(nums2) == 0: return [] d = dict() for num in nums1: d[num] = d.get(num, 0) + 1 ret = list() for num in nums2: if num in d and d[num] > 0: ret.append(num) d[num] -= 1 return ret# Runtime: 36 ms# Your runtime beats 100.00 % of python3 submissions.
复杂度分析同上。
类似的 Python 实现
from collections import Counterclass Solution: def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ counts = Counter(nums1) ret = list() for num in nums2: if counts[num] > 0: ret.append(num) counts[num] -= 1 return ret # Runtime: 36 ms# Your runtime beats 100.00 % of python3 submissions.
复杂度分析同上。
方法二：双指针
Java 实现
class Solution { public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int i = 0, j = 0, k = 0; int[] tmp = new int[nums1.length]; while (i < nums1.length && j < nums2.length) { if (nums1[i] < nums2[j]) { ++i; } else if (nums1[i] > nums2[j]) { ++j; } else { tmp[k++] = nums1[i]; ++i; ++j; } } int[] ret = new int[k]; for (int m = 0; m < k; ++m) { ret[m] = tmp[m]; } return ret; }}// Runtime: 1 ms// Your runtime beats 100.00 % of java submissions. 复杂度分析：
- 时间复杂度：\(O(nlog(n))\)
- 空间复杂度：\(O(n)\)
Python 实现
class Solution: def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ nums1, nums2 = sorted(nums1), sorted(nums2) i, j = 0, 0 ret = list() while True: try: if nums1[i] < nums2[j]: i += 1 elif nums1[i] > nums2[j]: j += 1 else: ret.append(nums1[i]) i += 1 j += 1 except IndexError: break return ret# Runtime: 40 ms# Your runtime beats 98.91 % of python3 submissions.
复杂度分析同上。