两数组交集算法(leetcode第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

算法一:

思路:

先排序,这样如果出现重复,可以筛查出来,保证唯一性

代码实现:
/**
 * 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;
}

最近更新

  1. 如何理解李彦宏说的“不要卷模型,要卷应用”

    2023-12-19 23:32:03       1 阅读
  2. 第一节 SHELL脚本中的常用命令(2)

    2023-12-19 23:32:03       1 阅读
  3. Python编程实例-处理Linux/UNIX系统中的信号

    2023-12-19 23:32:03       1 阅读
  4. 构造函数语意学(The Semantics of Constructors)

    2023-12-19 23:32:03       1 阅读
  5. PostgreSQL关闭数据库服务的三种模式

    2023-12-19 23:32:03       1 阅读

热门阅读

  1. 面试算法62:实现前缀树

    2023-12-19 23:32:03       35 阅读
  2. 网络 / day03 作业

    2023-12-19 23:32:03       38 阅读
  3. petalinux2021.1 手动打包BOOT.BIN

    2023-12-19 23:32:03       31 阅读
  4. Python设计模式

    2023-12-19 23:32:03       58 阅读
  5. C51--小车——串口/蓝牙控制及点动

    2023-12-19 23:32:03       43 阅读
  6. C语言之温度转换

    2023-12-19 23:32:03       27 阅读