[349. 两个数组的交集]（C语言）（两种解法：双指针+排序，哈希）

 

 ✨欢迎来到脑子不好的小菜鸟的文章✨

      🎈创作不易，麻烦点点赞哦🎈

          所属专栏：刷题   

          我的主页：脑子不好的小菜鸟

          文章特点：关键点和步骤讲解放在

          代码相应位置

 前提：

看本文章之前，建议先看看这篇对哈希算法的讲解哦，可能事半功倍哦~

传送门：常见的三种哈希结构（数组，set，map）-CSDN博客

题目链接：

349. 两个数组的交集 - 力扣（LeetCode）

AC代码：

法一：双指针+排序

qsort函数不了解的可看我之前的文章：qsort函数的使用和模拟实现排序-CSDN博客

/*法一*/
/*思路：排序+双指针*/


// int cmp(const void* e1, const void* e2)
// {
//     return *(int*)e1 - *(int*)e2;
// }

// int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
// {
//     int book[1005] = { 0 };
//     //要有一个标记的数组，防止数组中出现重复的数

//     qsort(nums1, nums1Size, sizeof(nums1[0]), cmp);
//     qsort(nums2, nums2Size, sizeof(nums2[0]), cmp);

//     int a = nums1Size < nums2Size ? nums1Size : nums2Size;
//     int* c = (int*)malloc(a * sizeof(nums1[0]));

//     int i = 0, j = 0, h = 0;
//     //i:nums1的下标 j:nums2的下标   h:c的下标
//     while (i < nums1Size && j < nums2Size)
//     {
//         if(nums1[i] == nums2[j])
//         {
//             if (book[nums1[i]] == 0)
//             {
//                 book[nums1[i]] = 1;
//                 c[h] = nums1[i];
//                 h++;
//             }
//             i++;
//             j++;
//         }
//         else if (nums1[i] > nums2[j])
//         {
//             j++;
//         }
//         else
//         {
//             i++;
//         }
//     }
  
//     *returnSize = h;
//     int* b = (int*)malloc(h * sizeof(nums1[0]));
//     for (int i = 0; i < h; i++)
//     {
//         b[i] = c[i];
//     }

//     return b;
// }

 法二：哈希表

/*法二：哈希表*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
    int h=0;
    int hash[1001]={0};
    int i=0;
    int max=nums1Size<nums2Size?nums1Size:nums2Size;
    

    for(i=0;i<nums1Size;i++)
    {
        hash[nums1[i]]=1;
    }

    int j=0;
    int* ans=(int*)calloc(max,sizeof(nums1[0]));

    for(i=0;i<nums2Size;i++)
    {
        if(hash[nums2[i]]==1)
            {
                ans[j++]=nums2[i];
                hash[nums2[i]]=0;
                /*!!!!!!!记得置为0，否则最后ans中的数量可能大于max，因为可能有很多个重复出现的元素反复放入ans!!!!!!!!!*/
            }
    }

    *returnSize=j;
    return ans;
}

 最后祝大家题题AC，只盼做个WA梦 ~