两个数组计算交加

题目形容

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

示例

 示例 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;}