Sponsored
Sponsored
This approach involves using a hash map (or dictionary) to keep track of the frequencies of elements in one of the arrays, then iterating through the second array to identify common elements, decrementing the frequency count accordingly.
Time Complexity: O(n + m), where n and m are the lengths of nums1 and nums2. Space Complexity: O(min(n, m)) due to the counter.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] Intersect(int[] nums1, int[] nums2) {
6 Dictionary<int, int> map = new Dictionary<int, int>();
7 List<int> result = new List<int>();
8 foreach (int num in nums1) {
9 if (map.ContainsKey(num))
10 map[num]++;
11 else
12 map[num] = 1;
13 }
14 foreach (int num in nums2) {
15 if (map.ContainsKey(num) && map[num] > 0) {
16 result.Add(num);
17 map[num]--;
18 }
19 }
20 return result.ToArray();
21 }
22}C# utilizes a Dictionary to store frequencies of nums1's elements. For nums2, it checks the presence and positive count of intersections in the dictionary, decrementing count post-addition.
Another efficient way is to first sort both arrays and then use two pointers to identify intersections. This approach harnesses the ordered nature post-sort to efficiently match elements by moving through both arrays simultaneously.
Time Complexity: O(n log n + m log m) due to sorting of nums1 and nums2. Space Complexity: O(1) extra space is used, aside from the outputs.
1Both arrays are initially sorted, and two pointers i and j iterate from the start of nums1 and nums2 respectively, by comparing elements. If matching, we add to the result; else, movements depend on comparatives.