网站建设商务代表工作总结,高效网站推广公司,网站开发 语言 架构 数据库,最适合女生的专业排名leetcode350. 两个数组的交集 II
给你两个整数数组 nums1 和 nums2 #xff0c;请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数#xff0c;应与元素在两个数组中都出现的次数一致#xff08;如果出现次数不一致#xff0c;则考虑取较小值#xff09;。可…leetcode350. 两个数组的交集 II
给你两个整数数组 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
题目分析
题目描述
给定两个整数数组 nums1 和 nums2返回两个数组的交集。输出结果中的每个元素出现的次数应与元素在两个数组中出现的次数一致。
算法分析
这个问题可以通过哈希表无序映射来解决。我们使用两个哈希表p1 和 p2来存储两个数组中每个元素的出现次数。然后我们遍历第一个哈希表对于每个元素如果它在第二个哈希表中也存在则计算两个哈希表中该元素出现次数的最小值并将其添加到结果数组中。
算法步骤
初始化两个哈希表 p1 和 p2。遍历数组 nums1将每个元素及其出现次数存储在 p1 中。遍历数组 nums2将每个元素及其出现次数存储在 p2 中。初始化一个空向量 res 来存储结果。遍历 p1对于每个元素 k 如果 p2 中包含 k则找到 p2 中 k 的位置。计算 p1 中 k 的出现次数和 p2 中 k 的出现次数的最小值。将 k 添加到 res 中次数为最小值。 返回 res。
算法流程 #mermaid-svg-Iv49tFyR17FPueHb {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-Iv49tFyR17FPueHb .error-icon{fill:#552222;}#mermaid-svg-Iv49tFyR17FPueHb .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-Iv49tFyR17FPueHb .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-Iv49tFyR17FPueHb .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-Iv49tFyR17FPueHb .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-Iv49tFyR17FPueHb .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-Iv49tFyR17FPueHb .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-Iv49tFyR17FPueHb .marker{fill:#333333;stroke:#333333;}#mermaid-svg-Iv49tFyR17FPueHb .marker.cross{stroke:#333333;}#mermaid-svg-Iv49tFyR17FPueHb svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-Iv49tFyR17FPueHb .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-Iv49tFyR17FPueHb .cluster-label text{fill:#333;}#mermaid-svg-Iv49tFyR17FPueHb .cluster-label span{color:#333;}#mermaid-svg-Iv49tFyR17FPueHb .label text,#mermaid-svg-Iv49tFyR17FPueHb span{fill:#333;color:#333;}#mermaid-svg-Iv49tFyR17FPueHb .node rect,#mermaid-svg-Iv49tFyR17FPueHb .node circle,#mermaid-svg-Iv49tFyR17FPueHb .node ellipse,#mermaid-svg-Iv49tFyR17FPueHb .node polygon,#mermaid-svg-Iv49tFyR17FPueHb .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-Iv49tFyR17FPueHb .node .label{text-align:center;}#mermaid-svg-Iv49tFyR17FPueHb .node.clickable{cursor:pointer;}#mermaid-svg-Iv49tFyR17FPueHb .arrowheadPath{fill:#333333;}#mermaid-svg-Iv49tFyR17FPueHb .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-Iv49tFyR17FPueHb .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-Iv49tFyR17FPueHb .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-Iv49tFyR17FPueHb .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-Iv49tFyR17FPueHb .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-Iv49tFyR17FPueHb .cluster text{fill:#333;}#mermaid-svg-Iv49tFyR17FPueHb .cluster span{color:#333;}#mermaid-svg-Iv49tFyR17FPueHb div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-Iv49tFyR17FPueHb :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 开始 初始化无序映射 p1 和 p2 遍历 nums1 存储 nums1 元素在 p1 遍历 nums2 存储 nums2 元素在 p2 初始化空向量 res 遍历 p1 检查 p2 中是否包含 k 找到 p2 中 k 的位置 计算 p1 中 k 的出现次数和 p2 中 k 的出现次数的最小值 将 k 添加到 res 中 次数为最小值 返回 res 结束 具体代码
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {unordered_mapint,int p1;unordered_mapint,int p2;for(int i0;inums1.size();i){p1[nums1[i]];}for(int i0;inums2.size();i){p2[nums2[i]];}vectorint res;for(auto k:p1){if(p2.count(k.first)){auto tp2.find(k.first);int p1sizek.second;int p2sizet-second; int sizemin(p1size,p2size);for(int j0;jsize;j){res.push_back(k.first);}}}return res;}
};算法分析
复杂度分析
时间复杂度O(mn)其中 m 和 n 分别是两个数组的长度。我们只需要遍历两个数组一次。空间复杂度O(mn)我们需要存储两个数组的元素及其出现次数这取决于数组的长度。
易错点
在初始化两个无序映射时确保正确地存储每个元素及其出现的次数。在比较两个映射中的元素时确保正确地使用 count 函数。在计算最小出现次数时确保正确地使用 min 函数。
注意事项
确保在遍历数组时不要超出数组的边界。在处理映射时确保不会覆盖任何元素。
相似题目
题目链接两个数组的交集 IIhttps://leetcode.com/problems/intersection-of-two-arrays-ii/数组交集https://leetcode.com/problems/intersection-of-two-arrays/查找重复的子树https://leetcode.com/problems/find-duplicate-subtrees/两数之和https://leetcode.com/problems/two-sum/
