[哈希]leetcode349. 两个数组的交集

题目

给定两个数组 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().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
   int i=0;
   int arr[1000]={0};
   int*ptr=(int*)malloc(sizeof(int)*1000);
   int index=0;
   for(i=0;i<nums1Size;i++)
   {
     arr[nums1[i]]++;
   }
   for(i=0;i<nums2Size;i++)
   {
       if(arr[nums2[i]]>0)
       {
           ptr[index++]=nums2[i];
           arr[nums2[i]]=0;
       }
   }
   *returnSize=index;
   return ptr;
}

过程分析

1

假设nums1和nums2分别为如图所示

2

首先mallc创建arr1数组，使其下标与值一一对应

3

如果出现了nums1的中的数字，就在arr1数组对应位置+1， 此时arr1中的下标对应表示，1出现了次，2出现了2次

4

arr1[nums2]=arr1[2]

判断此时arr1数组中下标为2的是否>0，若大于0则说明两者都有数据， 同时为了避免重复查找，将此时的arr1[2]=0