两数组交集算法(leetcode第349题)

2023-12-18 23:04:21

题目描述:

给定两个数组 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().
 */
# include<stdlib.h>
int cmp(const void *a,const void *b){
    return *(int*)a-*(int*)b;
}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    *returnSize=0;
    int *arr=(int*)malloc(sizeof(int)*(nums1Size+nums2Size));
    //先排序
    qsort(nums1,nums1Size,sizeof(int),cmp);
    qsort(nums2,nums2Size,sizeof(int),cmp);
    int index1=0,index2=0;
    while(index1<nums1Size && index2<nums2Size){
        int n1=nums1[index1],n2=nums2[index2];
        if(n1==n2){
            //保证唯一性
            if(!*(returnSize) || n1!=arr[(*returnSize)-1]){
                arr[(*returnSize)++]=n1;
            }
            index1++,index2++;
        }
        else if(n1<n2) index1++;
        else index2++;
    }
    return arr;
}

算法二:

思路:

使用hash表,先将nums1记录,再遍历nums2,若有nums2[j]在hash表中被记录过,则说明这是交集,存入返回的数组

代码实现:
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
# include<stdlib.h>
int hash_map[1001];
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){
    int *ret = NULL;
    int length = fmax(nums1Size, nums2Size);
    *returnSize = 0;
    ret = malloc(length * sizeof(int));
    memset(hash_map, 0, 1001 * sizeof(int));
    for (int i = 0; i < nums1Size; i++) {
        hash_map[nums1[i]] = 1;
    }
    for (int i = 0; i < nums2Size; i++) {
        if (hash_map[nums2[i]] == 1) {
            //nums2[i]被记录过-->交集
            ret[(*returnSize)++] = nums2[i];
            hash_map[nums2[i]] = 2;
        }
    }
    return ret;
}

文章来源:https://blog.csdn.net/Xudong_12345/article/details/135072164
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。