两数组交集算法(leetcode第349题)

题目描述：

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。示例 1：输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的提示：1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

算法一：

思路：

先排序，这样如果出现重复，可以筛查出来，保证唯一性

代码实现：

/*** Note: The returned array must be malloced, assume caller calls free().*/
# include<stdlib.h>
int cmp(const void *a,const void *b){return *(int*)a-*(int*)b;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {*returnSize=0;int *arr=(int*)malloc(sizeof(int)*(nums1Size+nums2Size));//先排序qsort(nums1,nums1Size,sizeof(int),cmp);qsort(nums2,nums2Size,sizeof(int),cmp);int index1=0,index2=0;while(index1<nums1Size && index2<nums2Size){int n1=nums1[index1],n2=nums2[index2];if(n1==n2){//保证唯一性if(!*(returnSize) || n1!=arr[(*returnSize)-1]){arr[(*returnSize)++]=n1;}index1++,index2++;}else if(n1<n2) index1++;else index2++;}return arr;
}

算法二：

思路：

使用hash表，先将nums1记录，再遍历nums2，若有nums2[j]在hash表中被记录过，则说明这是交集，存入返回的数组

代码实现：

/*** Note: The returned array must be malloced, assume caller calls free().*/
# include<stdlib.h>
int hash_map[1001];
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){int *ret = NULL;int length = fmax(nums1Size, nums2Size);*returnSize = 0;ret = malloc(length * sizeof(int));memset(hash_map, 0, 1001 * sizeof(int));for (int i = 0; i < nums1Size; i++) {hash_map[nums1[i]] = 1;}for (int i = 0; i < nums2Size; i++) {if (hash_map[nums2[i]] == 1) {//nums2[i]被记录过-->交集ret[(*returnSize)++] = nums2[i];hash_map[nums2[i]] = 2;}}return ret;
}