Algorithm
Problem Name: 350. Intersection of Two Arrays II
Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9] Explanation: [9,4] is also accepted.
Constraints:
1 <= nums1.length, nums2.length <= 10000 <= nums1[i], nums2[i] <= 1000
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#if 1
typedef struct e_s {
int val;
int cnt;
struct e_s *shadow;
} e_t;
#define HF 1021
e_t *lookup(e_t **ht, int v) {
int hc = v % HF;
e_t *e = ht[hc];
while (e && e->val != v) e = e->shadow;
return e;
}
void insert(e_t **ht, e_t *e) {
int hc = e->val % HF;
e->shadow = ht[hc];
ht[hc] = e;
}
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
e_t *e, *buff, *ht[HF] = { 0 };
int i, v;
int k, *result;
*returnSize = 0;
if (!nums1Size || !nums2Size) {
return NULL;
}
buff = malloc(nums2Size * sizeof(e_t));
//assert(buff);
for (i = 0; i < nums2Size; i ++) {
v = nums2[i];
e = lookup(ht, v);
if (e) e->cnt ++;
else {
e = &buff[i];
e->val = v;
e->cnt = 1;
insert(ht, e);
}
}
k = 0;
result = malloc(nums1Size * sizeof(int));
//assert(result);
for (i = 0; i < nums1Size; i ++) {
v = nums1[i];
e = lookup(ht, v);
if (e && e->cnt > 0) {
result[k ++] = v;
e->cnt --;
}
}
free(buff);
*returnSize = k;
return result;
}
#else
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int i, j, k;
int *result, *flags;
if (nums1Size > nums2Size) {
return intersect(nums2, nums2Size, nums1, nums1Size, returnSize);
}
*returnSize = 0;
if (!nums1Size || !nums2Size) {
return NULL;
}
result = malloc(nums1Size * sizeof(int));
flags = calloc(nums2Size, sizeof(int));
//assert(result && flags);
k = 0;
for (i = 0; i < nums1Size; i ++) {
for (j = 0; j < nums2Size; j ++) {
if (!flags[j] && nums1[i] == nums2[j]) {
result[k++] = nums1[i];
flags[j] = 1;
break;
}
}
}
*returnSize = k;
free(flags);
return result;
}
#endif
Input
nums1 = [1,2,2,1], nums2 = [2,2]
Output
[2,2]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map map = Arrays.stream(nums1).boxed()
.collect(Collectors.groupingBy(Function.identity(), HashMap::new, Collectors.counting()));
List < Integer> result = new ArrayList<>();
for (int num : nums2) {
if (map.getOrDefault(num, 0L) > 0) {
result.add(num);
map.put(num, map.get(num) - 1);
}
}
return result.stream().mapToInt(Integer::valueOf).toArray();
}
}
Input
nums1 = [1,2,2,1], nums2 = [2,2]
Output
[2,2]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const intersect = function(nums1, nums2) {
const res = []
const map = {}
for(let i = 0; i < nums1.length; i++) {
if(map.hasOwnProperty(nums1[i])) {
map[nums1[i]] += 1
} else {
map[nums1[i]] = 1
}
}
for(let j = 0; j < nums2.length; j++) {
if(map.hasOwnProperty(nums2[j]> && map[nums2[j]] > 0) {
res.push(nums2[j])
map[nums2[j]] -= 1
}
}
return res
};
Input
nums1 = [1,2,2,1], nums2 = [2,2]
Output
[2,2]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
intersect = lambda *x: [k for k, v in (collections.Counter(x[1]) & collections.Counter(x[2])).items() for _ in range(v)]
Input
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output
[4,9]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0350_IntersectionOfTwoArraysII
{
public int[] Intersect(int[] nums1, int[] nums2)
{
if (nums2.Length < nums1.Length) return Intersect(nums2, nums1);
var counts = new Dictionary<int, int>();
foreach (var num in nums1)
{
if (!counts.ContainsKey(num))
counts[num] = 1;
else
counts[num]++;
}
var result = new List < int>();
foreach (var num in nums2)
{
if (counts.ContainsKey(num) && counts[num] > 0)
{
result.Add(num);
counts[num]--;
}
}
return result.ToArray();
}
}
}
Input
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output
[4,9]