【Leetcode -349.两个数组的交集 -350.两个数组的交集Ⅱ】

简介: 【Leetcode -349.两个数组的交集 -350.两个数组的交集Ⅱ】

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

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
    {
        //因为两个数组的长度都是1000,所以开辟一个长度为1000数组,并将创建一个hash数组初始化为0
        //len为返回数组的长度
        int* p = (int*)malloc(sizeof(int) * 1000);
        int len = 0;
        int hash[1000] = { 0 };
        //将数组nums1中的每个元素作为hash数组的下标,若出现过就标记为1,若多次出现的仍标记为1
        for (int i = 0; i < nums1Size; i++)
        {
            hash[nums1[i]] = 1;
        }
        //遍历nums2数组,检查以nums2作为hash数组的下标,若以这个数作为下标的hash数组中的数已经被标记为1,
        //证明已经出现过,就将它放进已开辟好的数组p中,并记录len的长度,还要把标记为1的改成0
        for (int i = 0; i < nums2Size; i++)
        {
            if (hash[nums2[i]])
            {
                p[len++] = nums2[i];
                hash[nums2[i]] = 0;
            }
        }
        //返回数组的长度改成len
        *returnSize = len;
        return p;
    }

Leetcode - 350.两个数组的交集Ⅱ

给你两个整数数组 nums1 和 nums2 ,请你以数组形式返回两数组的交集。

返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。

示例 1:

输入:nums1 = [1, 2, 2, 1], nums2 = [2, 2]

输出:[2, 2]

示例 2:

输入:nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

输出:[4, 9]

提示:

1 <= nums1.length, nums2.length <= 1000

0 <= nums1[i], nums2[i] <= 1000

int* intersect(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
    {
        //开辟空间长度为1001的数组,用k记录p数组的长度;并将创建一个hash数组初始化为0
        int* p = (int*)malloc(sizeof(int) * 1001);
        int k = 0;
        int hash[1001] = { 0 };
        //遍历nums1数组,以数组中出现过的数作为hash数组的下标
        //每次相同的数字出现都累加起来
        for (int i = 0; i < nums1Size; i++)
        {
            hash[nums1[i]] += 1;
        }
        //遍历nums2数组,检查以nums2数组中的数作为下标的hash数组的位置的数是否大于0
        //大于0证明这个数也在nums1数组中出现过,将它放进p数组,并记录p的数组长度k
        //随后将这个数作为下标的hash数组的位置自减1,若这个数多次出现的话,这个位置仍不为0
        for (int i = 0; i < nums2Size; i++)
        {
            if (hash[nums2[i]] > 0)
            {
                p[k++] = nums2[i];
                hash[nums2[i]] -= 1;
            }
        }
        //返回数组的长度
        *returnSize = k;
        return p;
    }
目录
相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
40 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
68 0
|
2月前
|
C++
【LeetCode 12】349.两个数组的交集
【LeetCode 12】349.两个数组的交集
17 0
|
4月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
4月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
4月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组