《力扣刷题》 数据结构入门（两个数组的交集 II）

题目描述

若存在两个整数数组 nums1 和 nums2 ，需要我们以数组形式返回两数组的交集

特别注意！！！

        返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（并以最小出现次数输出），我觉得说到这里还是有一部分人不能理解，那么我举几个例子

        若存在   ，那么此处是不是应该返回  呢？因为符合 2 这个元素在两个数组中出现的次数都为 2 这个条件；但是此处还有一个限制条件（以最小出现次数输出），也就是说此处可以看成两个 2 元素，分别出现 1 次，那么就应该返回 

        若存在   ，那么此处是不是应该返回  呢？因为符合 4 和 5 这两个元素在两个数组中出现的次数都为 1 这个条件；哈哈哈，我们的猜想是对的，此处的确应该返回  

C 语言具体代码实现

又是作者本人没有思路的一天！！！所以鉴赏一下官方的方法：排序 + 双指针

        若两个数组是有序的，则可以使用双指针的方法得到两个数组的交集        

首先对两个数组进行排序，然后使用两个指针遍历两个数组

        初始时，两个指针分别指向两个数组的头部，每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位（当至少有一个指针超出数组范围时，遍历结束）

#include 
#include 
#include 
 
int cmp(const void *_a, const void *_b){
    int *a = (int*)_a;
    int *b = (int*)_b;
    return *a - *b;  // 升序
}

int *intersect(int *nums1, int nums1Size, int *nums2, int nums2Size, int *returnSize){
    // 将二个数组按升序排列
    qsort(nums1, nums1Size, sizeof(int), cmp);
    qsort(nums2, nums2Size, sizeof(int), cmp);
    *returnSize = 0;
    // 创建一个待返回的数组
    int *intersection = (int*)malloc(sizeof(int)*fmin(nums1Size, nums2Size));
    int index1 = 0, index2 = 0;
    while(index1 < nums1Size && index2 < nums2Size){  // 二个指针都不能越界
        if(nums1[index1] < nums2[index2]){
            index1++;
        }else if(nums2[index2] < nums1[index1]){
            index2++;
        }else{
            intersection[(*returnSize)++] = nums1[index1];
            index1++;
            index2++;
        }
    }
    return intersection;
}

int main(void){
	int nums_1[] = {1, 2, 3, 4, 5, 6};
	int nums_2[] = {3, 5, 6, 7, 8, 9};
	int return_size;
	int *return_arr = intersect(nums_1, 6, nums_2, 6, &return_size); 
	
	// 格式化输出
	printf("[");
	for(int i = 0; i < return_size; i++){
		if(i != return_size-1){
			printf("%d,", return_arr[i]);
		}else{
			printf("%d", return_arr[i]);
		}
	}
	printf("]");
	// [3,5,6]
	return 0;
}

官方还给出了哈希表的方法！！！但是作者不会，哈哈哈