leetcode刷题--基础数组--两个数组的交集（C）

1. 给定两个数组，编写一个函数来计算它们的交集。
   示例 1:
   输入: nums1 = [1,2,2,1], nums2 = [2,2]
   输出: [2,2]
   示例 2:
   输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
   输出: [4,9]
   说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。

思想：（1）将两个数组进行排序O(nlgn)然后依次O(n)比较转存。时间复杂度为O(nlgn)，空间复杂度为O(1)， 但破坏了原数组。排序函数一般使用各语言自带的函数效率较高，所以这边我默认为两个数组已经排序完成。

int intersect(int* nums1, int nums1Size, int* nums2, int nums2Size){
	int i=0, j=0;
	int count=0;
	if(nums1Size<nums2Size)
        int *intersect = (int *)malloc(nums1Size*sizeof(int));
    else
    	int *intersect = (int *)malloc(nums2Size*sizeof(int));
	while(i == j){
		if(nums1[i] == nums2[j]){
			intersect[count++] = nums1[i];
			i++;
			j++;
		}
		else if(nums1[i] > nums2[j])
			j++;
		else
			i++;
	}
	return count;
}

（2）暴力解法。直接用短数组为基准，将其中的元素一个个拿出来跟长数组中的元素比较，如果相同则存储，并且将该元素所在长数组的位置做标记，避免重复。时间复杂度O(n^2)，空间复杂度O(n)，如果不想使用空间可以在原长数组中进行修改，改成不可比较的值，这样会破坏原数组。

tersect(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int count = 0;
    if(nums1Size<nums2Size){
        printf("1");
        int *flag = (int *)malloc(nums2Size*sizeof(int));
        int *intersect = (int *)malloc(nums1Size*sizeof(int));
        for(int j=0; j<nums2Size; j++){
            flag[j] = 0;
        }
        for(int i=0; i<nums1Size; i++){
            for(int j=0; j<nums2Size; j++){
                if((flag[j]==0) && (nums1[i] == nums2[j])){
                    intersect[count] = nums1[i];
                     printf("%d", intersect[count]);
                    count++;
                    flag[j] = 1;
                }
            }
        }
    }
    else{
        int *flag = (int *)malloc(nums1Size*sizeof(int));
        int *intersect = (int *)malloc(nums2Size*sizeof(int));
        for(int i=0; i<nums1Size; i++){
            flag[i] = 0;
        }
        for(int j=0; j<nums2Size; j++){
            for(int i=0; i<nums1Size; i++){
                if((flag[i]==0) && (nums1[i] == nums2[j])){
                    intersect[count] = nums2[j];
                    printf("%d", intersect[count]);
                    count++;
                    flag[i] = 1;
                }
            }
        }
    }
    return count;
}

（3）哈希表。把两个数组A和B都遍历到一个新的数组里，然后在统计重复的数字即可，这个时间复杂度就是O(n)，空间复杂度O(m)。这个要求数组内数字的范围是已知并且不是很大。同样的在JAVA里面有HashMap。