
问题
给定两个数组,编写一个函数来计算它们的交集。
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
Given two arrays, write a function to compute their intersection.
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Note:
Each element in the result must be unique.
The result can be in any order.
示例
public class Program { public static void Main(string[] args) { var nums1 = new int[] { 1, 2, 2, 1 }; var nums2 = new int[] { 2, 2 }; var res = Intersection(nums1, nums2); ShowArray(res); nums1 = new int[] { 4, 9, 5 }; nums2 = new int[] { 9, 4, 9, 8, 4 }; res = Intersection2(nums1, nums2); ShowArray(res); Console.ReadKey(); } private static void ShowArray(int[] array) { foreach(var num in array) { Console.Write($"{num} "); } Console.WriteLine(); } private static int[] Intersection(int[] nums1, int[] nums2) { var set = new HashSet<int>(); foreach(var i in nums1) { if(!set.Contains(i)) set.Add(i); } var list = new List<int>(); var set2 = new HashSet<int>(); foreach(var k in nums2) { if(set.Contains(k) && !set2.Contains(k)) { list.Add(k); set2.Add(k); } } return list.ToArray(); } private static int[] Intersection2(int[] nums1, int[] nums2) { return nums1.Intersect(nums2).ToArray(); } }
以上给出2种算法实现,以下是这个案例的输出结果:
2 4 9
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4042。