【LeetCode】初级算法-两个数组的交集 II

wind3110991 发布于2019-08-23 11:43 / 2242人阅读

摘要：题目描述两个数组的交集给定两个数组，编写一个函数来计算它们的交集。示例输入输出示例输入输出说明输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。

题目描述

两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。

示例 1:

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

示例 2:

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

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

进阶:

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

思路

排序，遍历比较
用pos1指针遍历nums1,pos2指针遍历nums2
如果nums1(pos1)==nums2(pos2),则放入交集nums3中;
如果nums1(pos1)>nums2(pos2),则pos1++;
否则pos2++.

JavaScript实现

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    nums1.sort(cmp);
    nums2.sort(cmp);
    //console.log(nums1.join(","));
    //console.log(nums2.join(","));
    let pos1 = 0;
    let pos2 = 0;
    let nums3 = [];
    while(pos1 < nums1.length && pos2 < nums2.length){
        if(nums1[pos1] == nums2[pos2]){
            nums3.push(nums1[pos1]);
            pos1++;
            pos2++;
         }else if(nums1[pos1] > nums2[pos2]){
            pos2++;
         }else{
            pos1++;
         }
    }
    return nums3;
};
function cmp(x,y){
    return x-y;
}

云服务器 GPU云服务器交集数组 php 取交集算法算法正则 java 交集两个数组

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97364.html

【刷算法】LeetCode.350-两个数组的交集 II

摘要：数据结构给定两个数组，编写一个函数来计算它们的交集。示例输入输出示例输入输出说明输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。数据结构给定两个数组，编写一个函数来计算它们的交集。示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2,2] 示例 2: 输入: nums1 = [4,9,5...

printempw 2019-08-23 11:49 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
JavaScript数据结构与算法-Array-(leetcode原题)

摘要：的最大公约数是，记为，，。示例输入输出示例输入输出注意数组内已种好的花不会违反种植规则。输入的数组长度范围为。是非负整数，且不会超过输入数组的大小。博客原文地址： https://finget.github.io/2019... 只出现一次的数字i 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线...

joy968 2019-08-26 13:51 评论0 收藏0
70道前端LeetCode题目集合及视频讲解（持续更新中...）

前端LeetCode刷题下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...

mayaohua 2019-08-26 10:46 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0