349. 两个数组的交集

题目描述

给定两个数组 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

思路

目的是找到两个数组 nums1 和 nums2 的交集，并将结果存储在一个动态分配的数组中返回。 解题方法采用暴力搜索法，即通过嵌套循环逐一比较两个数组中的元素。

解题过程

初始化结果数组和变量：

        首先确定结果数组的最大可能长度为两个输入数组中较小的那个数组的长度（len = nums1Size > nums2Size ? nums2Size : nums1Size）。

        动态分配一个大小为 len 的整型数组 res 用于存储交集结果。

        定义变量 index 用于记录实际存入结果数组的元素个数。

遍历第一个数组：

        使用外层循环遍历 nums1 中的每个元素。

        对于 nums1[i]，使用内层循环检查它是否存在于 nums2 中。

标记已匹配的元素：

        如果 nums1[i] 在 nums2 中找到，则将对应的 nums2[j] 标记为 -1，避免重复匹配。

        将匹配到的元素存入结果数组 res 中，并更新 index。

返回结果：

        最终将 returnSize 设置为 index，表示结果数组的实际长度。

        返回动态分配的结果数组。

复杂度

• 时间复杂度: O(n^2)

• 空间复杂度: O(n)

Code

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int len = nums1Size > nums2Size ? nums2Size : nums1Size;
    int* res = (int*)malloc(sizeof(int) * len);
    int index = 0;
    for (int i = 0; i < nums1Size; i++){
        int flag = 0;
        for (int j = 0; j < nums2Size; j++){
            if(nums1[i] == nums2[j]){
                flag = 1;
                nums2[j] = -1;
            }
        }
        if(flag == 1){
            res[index++] = nums1[i];
        }
    }
    *returnSize = index;
    return res;
}