[C++知识库]LeetCode 350. 两个数组的交集II 哈希表法 C语言 Intersection of Two Arrays II

本篇文章为笔者的LeetCode刷题笔记。文章整体分为两部分：1.笔者自己思考的算法及代码。2.LeetCode官方给出的最优算法及代码。通过对比这两部分算法和代码的异同，笔者的算法思想和编程水平有了显著地提升。如果这篇文章能帮到你那真是再好不过了！?

一、读者思考的算法

A.算法：利用哈希表，将较短的数组1放入哈希表。再遍历较长的数组2，依次与哈希表中的存货比较。

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */         //注意此处返回数组必须是动态分配的才行
 
int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){

    typedef struct {
     int key;                 //C语言对哈希表的配置 定义一个包含键值和出现次数value的结构体
     int value;
     UT_hash_handle hh;
 } Hash;
 Hash *hash = NULL;        //声明一个指向该结构体的指针hash

 Hash * find(int key){        //在哈希表中查找是否存在给定key值，若存在返回指向其地址的指针
     Hash *tep = NULL;        //否则返回空指针
     HASH_FIND_INT(hash,&key,tep);
     return tep;
 }
 void insert(int key){        //将较小数组key值和其出现次数插入哈希表
     Hash * tep = find(key);
     if(tep==NULL){            //若找不到，则插入
         Hash *s = (Hash*)malloc(sizeof(Hash)); //动态分配一个结构体
         s->key=key;                             //给其赋值
         s->value=1;
         HASH_ADD_INT(hash,key,s);  //调用库函数，将s所指的Hash结构体插入到hash老巢中key映射的地址上
     }else{
         tep->value++; //若已存在，则出现次数++
     }
 }
    if(nums1Size<nums2Size){  
        int *ret = (int*)malloc(sizeof(int)*(nums1Size));
        *returnSize=0;
        for(int i=0;i<nums1Size;i++){        //将较小数组插入哈希表
            insert(nums1[i]);
        }
        for(int j=0;j<nums2Size;j++){        //依次查找较大数组各元素是否在哈希表中
            Hash *it = find(nums2[j]);
            if(it==NULL){}     //若不存在则为空，且此处必须加这一行，否则下一行it为空会报错
            else if(it->key==nums2[j]&&it->value!=0){ //当存在且哈希表中此key出现次数>0
                it->value--;        //出现次数--
                ret[(*returnSize)++]=nums2[j];    //将交集依次放入新建数组ret
            }        //注意此处*returnSize初始化为0，这样写可以省一个int index变量
        }
        return ret;    //返回该数组
    }else{
        int *ret = (int*)malloc(sizeof(int)*(nums2Size));
        *returnSize=0;
        for(int i=0;i<nums2Size;i++){
            insert(nums2[i]);
        }
        for(int j=0;j<nums1Size;j++){
            Hash *it = find(nums1[j]);
            if(it==NULL){}
            else if(it->key==nums1[j]&&it->value!=0){
                it->value--;
                ret[(*returnSize)++]=nums1[j];
            }
        }
        return ret;
    }
    

}

B.算法复杂度分析

时间复杂度：O(m+n) m和n依次为两个数组的长度。需要对两个数组依次遍历，再对哈希表进行操作。操作哈希表的时间复杂度为O(1)。

空间复杂度: O( min(m,n) ) m和n依次为两个数组的长度。哈希表中需要存放较小数组的元素，所以哈希表的大小不大于较小数组大小。返回数组也不大于较小数组的长度。

二.官方算法

官方算法与我的算法几乎一致

第二种算法是先排序再用双指针，很容易实现。

A.算法：

如果两个数组是有序的，则可以使用双指针的方法得到两个数组的交集。首先对两个数组进行排序，然后使用两个指针遍历两个数组。初始时，两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字，如果两个数字不相等，则将指向较小数字的指针右移一位，如果两个数字相等，将该数字添加到答案，并将两个指针都右移一位。当至少有一个指针超出数组范围时，遍历结束。

int cmp(const void* _a, const void* _b) {
    int *a = _a, *b = (int*)_b;
    return *a == *b ? 0 : *a > *b ? 1 : -1;
}

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 (nums1[index1] > nums2[index2]) {
            index2++;
        } else {
            intersection[(*returnSize)++] = nums1[index1];
            index1++;
            index2++;
        }
    }
    return intersection;
}

C.算法复杂度分析

时间复杂度：O(mlogm+nlogn)，其中?m 和?n 分别是两个数组的长度。对两个数组进行排序的时间复杂度是O(mlogm+nlogn)，遍历两个数组的时间复杂度是?O(m+n)，因此总时间复杂度是O(mlogm+nlogn)。
空间复杂度：O(min(m,n))，其中m 和?n分别是两个数组的长度。为返回值创建一个数组intersection，其长度为较短的数组的长度。

三.笔者小结

1. 通过这道题学会了哈希表的使用方法。哈希表查找操作的时间复杂度为O(1)。因为哈希表有专门的映射函数，可以只通过一步计算就得出key所对应的地址，而不用像数组或链表一样依次遍历查找。例如Hash(key)=key，Hash(1)=1，指的是key为1的地址就为1。

2. 用C实现哈希表的都是勇士，我是学完考研408四门专业课后直接开始刷LeetCode的，所以只会C语言。现在在慢慢自学Java了，用Java或者C++直接可以用几行代码就搞定C几十行。。。

3. 关于C语言哈希表的使用：https://blog.csdn.net/nameofcsdn/article/details/107297361

Keep calm and carry on!

谢谢你看到这里！