C#LeetCode刷题之#349-两个数组的交集(Intersection of Two Arrays)

C#LeetCode刷题之#349-两个数组的交集(Intersection of Two Arrays)

问题

给定两个数组,编写一个函数来计算它们的交集。

输入: 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种算法的时间复杂度均为: O(n)​ 。

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/4042

发表评论

登录后才能评论