class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
}
};
350. 两个数组的交集 II
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[4,9]
提示：
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
进阶：
nums1 的大小比 nums2 小，哪种方法更优？nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？原站题解
rust 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2025-01-30 10:20:42
use std::collections::HashMap;
impl Solution {
pub fn intersect(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
let mut cnt = HashMap::new();
for x in nums1 {
*cnt.entry(x).or_insert(0) += 1;
}
let mut ans = vec![];
for x in nums2 {
if let Some(c) = cnt.get_mut(&x) {
if *c > 0 {
*c -= 1;
ans.push(x);
}
}
}
ans
}
}
javascript 解法, 执行用时: 3 ms, 内存消耗: 50.9 MB, 提交时间: 2025-01-30 10:20:28
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) {
const cnt = new Map();
for (const x of nums1) {
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
const ans = [];
for (const x of nums2) {
const c = cnt.get(x) ?? 0;
if (c > 0) {
cnt.set(x, c - 1);
ans.push(x);
}
}
return ans;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 4.7 MB, 提交时间: 2025-01-30 10:20:14
func intersect(nums1, nums2 []int) (ans []int) {
cnt := map[int]int{}
for _, x := range nums1 {
cnt[x]++
}
for _, x := range nums2 {
if cnt[x] > 0 {
cnt[x]--
ans = append(ans, x)
}
}
return
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 14.7 MB, 提交时间: 2025-01-30 10:19:55
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> cnt;
for (int x : nums1) {
cnt[x]++;
}
vector<int> ans;
for (int x : nums2) {
if (cnt[x] > 0) {
cnt[x]--;
ans.push_back(x);
}
}
return ans;
}
//
vector<int> intersect2(vector<int>& nums1, vector<int>& nums2) {
unordered_multiset<int> st(nums1.begin(), nums1.end());
vector<int> ans;
for (int x : nums2) {
auto it = st.find(x);
if (it != st.end()) {
st.erase(it);
ans.push_back(x);
}
}
return ans;
}
};
java 解法, 执行用时: 5 ms, 内存消耗: 42.7 MB, 提交时间: 2025-01-30 10:19:18
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums1) {
cnt.merge(x, 1, Integer::sum); // cnt[x]++
}
List<Integer> ans = new ArrayList<>();
for (int x : nums2) {
int c = cnt.getOrDefault(x, 0);
if (c > 0) {
cnt.put(x, c - 1);
ans.add(x);
}
}
// 由于返回值是 int[]，需要额外遍历一次
return ans.stream().mapToInt(i -> i).toArray();
}
}
python3 解法, 执行用时: 3 ms, 内存消耗: 17.9 MB, 提交时间: 2025-01-30 10:19:04
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
cnt = Counter(nums1)
ans = []
for x in nums2:
if cnt[x] > 0:
cnt[x] -= 1
ans.append(x)
return ans
golang 解法, 执行用时: 0 ms, 内存消耗: 2.8 MB, 提交时间: 2021-07-15 09:28:49
func intersect(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
n1, n2 := len(nums1), len(nums2)
k1, k2 := 0, 0
nums3 := make([]int, 0, n1+n2)
for k1 < n1 && k2 < n2 {
if nums1[k1] < nums2[k2] {
k1++
} else if nums1[k1] > nums2[k2] {
k2++
} else {
nums3 = append(nums3, nums1[k1])
k1++
k2++
}
}
return nums3
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.8 MB, 提交时间: 2020-11-26 11:22:33
func intersect(nums1 []int, nums2 []int) []int {
sort.Ints(nums1)
sort.Ints(nums2)
ans := []int{}
index1, index2 := 0, 0
for index1 < len(nums1) && index2 < len(nums2) {
if nums1[index1] < nums2[index2] {
index1++
} else if nums1[index1] > nums2[index2] {
index2++
} else {
ans = append(ans, nums1[index1])
index1++
index2++
}
}
return ans
}
python3 解法, 执行用时: 76 ms, 内存消耗: 13.7 MB, 提交时间: 2020-11-26 10:54:06
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
if len(nums2) < len(nums1):
nums1, nums2 = nums2, nums1
ans = []
for i in nums1:
if i in nums2:
ans.append(i)
nums2.remove(i)
return ans