两个数组计算交加

题目形容

给定两个数组，编写一个函数来计算它们的交加。

示例

示例 1：输出：nums1 = [1,2,2,1], nums2 = [2,2]输入：[2]示例 2：输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]输入：[9,4]阐明：    输入后果中的每个元素肯定是惟一的。    咱们能够不思考输入后果的程序。

办法

办法一：bitmap + 与运算

1.创立两个bitmap：bitmap1、bitmap2，别离用 nums1、nums2 来初始化 bitmap1、bitmap2：将 nums1中的值作为 bitmap1 的索引，并将该索引对应的值置为 1；bitmap2 同理2.创立一个 result数组，用于保留后果3.bitmap1 和 bitmap2 一一元素进行 与运算，若 与运算后果为1，则将值赋值给 result，同时 (*resultSize)++，result中为 1 的元素就是交加，*resultSize就是交加元素个数

毛病：三个大数组，空间开销大

办法二：排序 + 比拟

1.qsort对两个数组排序2.创立result数组，大小为 nums1Size 和 nums2Size 中较小的那个2.一一比拟 nums1[i]、nums2[j]中的元素    若想等 并且 nums1[i] 不等于 prev，则将 nums1[i] 保留至result中，i++，j++    若不相等，将 nums1[i]、nums2[j] 中较小的值得索引向后偏移

代码

bitmap + 与运算

#define MAX 2048/** * Note: The returned array must be malloced, assume caller calls free(). */int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){    char *map1 = NULL;    char *map2 = NULL;    int index = 0;    int *result = NULL;        *returnSize = 0;    map1 = (char *)malloc(MAX*sizeof(char));    if (NULL == map1)    {        return NULL;    }    memset(map1, 0x00, MAX);    map2 = (char *)malloc(MAX*sizeof(char));    if (NULL == map2)    {        free(map1);        return NULL;    }    memset(map2, 0x00, MAX);    for(index = 0; index < nums1Size; index++)    {        map1[nums1[index]] = 1;    }    for(index = 0; index < nums2Size; index++)    {        map2[nums2[index]] = 1;    }    result = (int *)malloc(sizeof(int)*MAX);    if (NULL == result)    {        free(map1);        return NULL;    }    memset(result, 0x00, MAX);    for (index = 0; index < MAX; index++)    {        if (map1[index] & map2[index])        {            result[*returnSize] = index;            (*returnSize)++;        }    }    free(map1);    free(map2);    return result;}

排序

int *cmp(const void * a, const void * b){    return *(int *)a - *(int *)b;}/** * Note: The returned array must be malloced, assume caller calls free(). */int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){    int *result = NULL;    int i = 0;    int j = 0;    int pre;    /* 这里不能初始化为 0，否则遇到元素值为 0 的时候会出错 */    *returnSize = 0;    result = (int *)malloc(sizeof(int) * (nums1Size < nums2Size ? nums1Size : nums2Size));    if (NULL == result)    {        return NULL;    }    qsort(nums1, nums1Size, sizeof(int), cmp);    qsort(nums2, nums2Size, sizeof(int), cmp);    while (i < nums1Size && j < nums2Size)    {        if (nums1[i] == nums2[j] && pre != nums1[i])        {            result[(*returnSize)++] = nums1[i];            pre = nums1[i];            i++;            j++;        }        else        {            nums1[i] < nums2[j] ? i++ : j++;        }    }    return result;}int main(){        return 0;}