成都建站seo,世界互联网峰会马云,2022年注册公司流程,crm软件是什么意思题目描述
给定两个数组#xff0c;编写一个函数来计算它们的交集。
示例 1:
输入: nums1 [1,2,2,1], nums2 [2,2]
输出: [2]示例 2:
输入: nums1 [4,9,5], nums2 [9,4,9,8,4]
输出: [9,4]说明:
输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
解…题目描述
给定两个数组编写一个函数来计算它们的交集。
示例 1:
输入: nums1 [1,2,2,1], nums2 [2,2]
输出: [2]示例 2:
输入: nums1 [4,9,5], nums2 [9,4,9,8,4]
输出: [9,4]说明:
输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。
解题思路
使用哈希表统计一个数组中每个元素的出现次数然后遍历另一个数组找到与哈希表中相同元素将其添加到结果集中。
C#代码实现
public int[] Intersection(int[] nums1, int[] nums2) {// 创建一个HashSet用于存储nums1中的元素HashSetint set1 new HashSetint(nums1);// 创建一个HashSet用于存储nums2中的元素HashSetint set2 new HashSetint();// 遍历nums2如果nums1中包含nums2中的元素则将其添加到set2中foreach (int num in nums2) {if (set1.Contains(num)) {set2.Add(num);}}// 返回set2中的元素return set2.ToArray();
}C代码实现
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int* result (int*)malloc(sizeof(int) * (nums1Size nums2Size ? nums2Size : nums1Size));int resultSize 0;int* set1 (int*)malloc(sizeof(int) * nums1Size);int* set2 (int*)malloc(sizeof(int) * nums2Size);int set1Size 0;int set2Size 0;// 构建哈希表 set1for (int i 0; i nums1Size; i) {if (!contains(set1, set1Size, nums1[i])) {set1[set1Size] nums1[i];}}// 遍历数组 nums2找到与 set1 中相同的元素将其添加到 set2for (int i 0; i nums2Size; i) {if (contains(set1, set1Size, nums2[i]) !contains(set2, set2Size, nums2[i])) {set2[set2Size] nums2[i];}}// 将 set2 转为数组 resultfor (int i 0; i set2Size; i) {result[resultSize] set2[i];}*returnSize resultSize;return result;
}// 判断数组中是否包含某个元素
bool contains(int* arr, int size, int target) {for (int i 0; i size; i) {if (arr[i] target) {return true;}}return false;
}时间复杂度和空间复杂度
时间复杂度O(m n)其中 m 和 n 分别是数组 nums1 和 nums2 的长度。分别遍历两个数组一次。空间复杂度O(m n)其中 m 和 n 分别是数组 nums1 和 nums2 的长度。使用了两个哈希表。
