数据结构与算法之集合: Leetcode 349. 两个数组的交集 (Typescript版)
两个数组的交集
- https://leetcode.cn/problems/intersection-of-two-arrays/description/
描述
- 给定两个数组 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
算法实现
1 )使用数组filter+集合的has方法
function intersection (nums1: number[], nums2: number[]): number[] {return [...new Set(nums1)].filter(n => new Set(nums2).has(n)); // 这里filter内部函数每次都会new Set, 不合适
}
- 这个算法的问题是代码书写逻辑重复,或者说因编码经验而导致的性能低下
2 )使用数组filter+集合的has方法 优化版
function intersection (nums1: number[], nums2: number[]): number[] {const n2 = new Set(nums2);return [...new Set(nums1)].filter(n => n2.has(n));
}
- 只需要一次set, 无需循环中每次都做
3 )使用数组filter+数组includes方法或indexOf方法
function intersection (nums1: number[], nums2: number[]): number[] {return [...new Set(nums1)].filter(n => nums2.includes(n)); // 或 indexOf 来处理: nums2.indexOf(n) > -1
}
4 )排序 + 双指针
function intersection (nums1: number[], nums2: number[]): number[] {nums1.sort((x, y) => x - y);nums2.sort((x, y) => x - y);const length1 = nums1.length, length2 = nums2.length;let index1 = 0, index2 = 0;const intersection = [];while (index1 < length1 && index2 < length2) {const num1 = nums1[index1], num2 = nums2[index2];if (num1 === num2) {// 保证加入元素的唯一性if (!intersection.length || num1 !== intersection[intersection.length - 1]) {intersection.push(num1);}index1++;index2++;} else if (num1 < num2) {index1++;} else {index2++;}}return intersection;
}
- 这种是官方示例,代码实现比较复杂,主要依靠两个数组的同一规则排序
- 之后使用两个指针来指向当前元素,当两者相同时,如果唯一,则存储
- 在实际应用中,虽然效率上还行,但是并不推荐上述算法实践,代码冗余
- 时间复杂度主要在两个sort排序, nlogn + mlogm
- 空间复杂度也是在两个sort排序,logn + logm
TS中的集合扩展
1 )Set操作,使用Set对象:new、add、delete、has、size
let mySet = new set();
mySet.add(1);
mySet.add(5);
mySet.add(5); // 不会保留多个5,只会保留1个
mySet.add('ssse');
let o = {name: 1};
mySet.add(o);
mySet.add({name:1}); // 会保留两个对象,它们内存地址是不同的console.log(mySet.has(1)); // true
console.log(mySet.has(3)); // false
console.log(mySet.has(5)); // true
console.log(mySet.has('ssse')); // true
console.log(mySet.has(o)); // truemySet.delete(5);
2 )迭代Set
// 迭代1 for of 迭代
for(let item of mySet) console.log(item);
// 迭代2
for(let item of mySet.keys()) console.log(item);
// 迭代3
for(let item of mySet.values()) console.log(item); // 值同key
// 以上三种迭代, 输出结果一致// 下面通过entries()方法来调用
for(let [key, value] of mySet.entries()) console.log(key, value); // 打印key和value果然完全一样
3 )Set 和 Array互转
// Set转Array, 方式1
const myArr = [...mySet];
// Set转Array, 方式2
const myArr = Array.from(mySet);
// Array转Set
const mySet2 = new Set([1,2,3,4])
4 )Set的交集和差集
// 求两个Set交集
const intersection = new Set([...mySet].filter(x => mySet2.has(x)))// 求两个Set差集
const difference = new Set([...mySet].filter(x => !mySet2.has(x)))
相关文章:
数据结构与算法之集合: Leetcode 349. 两个数组的交集 (Typescript版)
两个数组的交集 https://leetcode.cn/problems/intersection-of-two-arrays/description/ 描述 给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1 输入:nums1 [1,2,…...
Unity 内存性能分析器 (Memory Profiler)
一、 安装 安装有两种方式一: add package : com.unity.memoryprofiler方式二: From Packages : Unity Registry 搜索 Memory Profiler 二、 使用 打开:Windows - > Analysis - > Memory Profiler 打开MemoryProfiler界面࿰…...
前端携带Bearer Token
前端携带Bearer Token 在前端使用 axios 发送请求时,可以通过设置请求头来携带 Bearer Token。Bearer Token 是一种常用的身份验证方式,它通常用于 OAuth2 授权流程中。 要在 axios 中携带 Bearer Token,可以通过设置 Authorization 请求头…...
leetcode 周赛 364
参考视频: 单调栈【力扣周赛 364】 文章目录 8048. 最大二进制奇数100049. 美丽塔 I100048. 美丽塔 II100047. 统计树中的合法路径数目 8048. 最大二进制奇数 题目链接 给你一个 二进制 字符串 s ,其中至少包含一个 1 。 你必须按某种方式 重新排列 字…...
开机自启动Linux and windows
1、背景 服务器由于更新等原因重启,部署到该服务上的响应的应用需要自启动 2、Linux 2.1 方式一 编写启动应用的sh脚本授权该脚本权限 chmod 777 xxx.sh 修改rc.loacl 位置:/etc/rc.local 脚本:sh /home/xxxx.sh & 授权rc.local …...
科技云报道:大模型的阴面:无法忽视的安全隐忧
科技云报道原创。 在AI大模型的身上,竟也出现了“to be or not to be”问题。 争议是伴随着大模型的能力惊艳四座而来的,争议的核心问题在于安全。安全有两个方面,一个是大模型带来的对人类伦理的思考,一个是大模型本身带来的隐…...
2023年前端流行什么技术和框架了?
Web前端三大主流框架有React、Vue.js和Angular,由于接触过Vue.js,接下来主讲最新的Vue3.0! Vue3.0作为最新版本的Vue.js框架,拥有更强大的性能和更丰富的功能,为低代码开发平台注入了全新的活力。而JNPF快速开发平台作…...
Nginx 背锅解析漏洞
Nginx 背锅解析漏洞 文章目录 Nginx 背锅解析漏洞1 在线漏洞解读:2 环境搭建3 影响版本:4 漏洞复现4.1 访问页面4.2 上传文件 4.3 上传失败4.4 使用bp进行分析包4.5 对返回图片位置进行访问4.6 执行php代码技巧-图片后缀加./php4.7 分析原因 --》cgi.fix_pathinfo--…...
AI与传统数据库 - ChatGPT风过之后 | 从Duet AI说开来
作者:Ni Demai,是NineData数据库产品专家,曾任阿里云数据库国际产品总负责人,华为高斯 GaussDB 创始团队核心架构师,IBM Db2 资深研发工程师。 Demai 专注 Cloud-Native database 架构设计,分析型 MPP&…...
L1-032 Left-pad C++解法
一、题目再现 根据新浪微博上的消息,有一位开发者不满NPM(Node Package Manager)的做法,收回了自己的开源代码,其中包括一个叫left-pad的模块,就是这个模块把javascript里面的React/Babel干瘫痪了。这是个…...
Python 用列表实现模拟手机通讯录(简易版)
"""列表实现好友管理系统知识点:1、列表存储信息2、列表增删改查3、嵌套循环4、字符串分割和拼接(重点)5、列表索引"""# 暂存好友信息(程序结束数据删除) friend_info list()input_buf…...
macOS使用官方安装包安装python
新手程序员可能想知道如何在 Mac 上正确安装 Python,这里介绍在 macOS 上安装 Python 的方法。 操作步骤 1.从 Python 官方网站 (python.org) 下载最新的 Python 版本. 单击 macOS 链接并选择最新的 Python 版本。 2.下载完成后,双击包开始安装Python…...
如何重装Windows Mirosoft Store
重装Windows Mirosoft Store 如何重装Windows Mirosoft Store呢?如何下载Windows Mirosoft Store呢?Windows Mirosoft Store不见了咋办?Windows 自带软件不见了咋办等等?写在前面 1.文件准备2.安装 如何重装Windows Mirosoft Stor…...
软考高级系统架构设计师系列论文真题七:基于构件的软件开发
软考高级系统架构设计师系列论文真题七:基于构件的软件开发 一、基于构件的软件开发二、找准核心论点三、理论素材准备四、精品范文赏析1.摘要2.正文3.总结软考高级系统架构设计师系列论文之:百篇软考高级架构设计师论文范文软考高级系统架构设计师系列之:论文题目类型、论文…...
git rebase 修改中间的commit
0. 前言 今天在移植最新版本 kfence 功能的时候,一共需要移植大概40多个 patch,中间有很多patch 存在冲突,需要手动修改后才能合并。当所有的patch 都合并完成进行编译的时候,发现其中一个 patch 手动合并出了个错误。 假如共有…...
登录业务实现 - token登录鉴权
登录业务实现: 登录成功/失败实现 -> pinia管理用户数据及数据持久化 -> 不同登录状态的模板适配 -> 请求拦截器携带token(登录鉴权) -> 退出登录实现 -> token失效(401响应拦截) 1. 登录成…...
内存对齐--面试常问问题和笔试常考问题
1.内存对齐的意义 C 内存对齐的主要意义可以简练概括为以下几点: 提高访问效率:内存对齐可以使数据在内存中以更加紧凑的方式存储,从而提高了数据的访问效率。处理器通常能够更快地访问内存中对齐的数据,而不需要额外的字节偏移计…...
贪心算法-会议室问题
1、题目描述 一些项目要占用一个会议室宣讲,会议室不能同时容纳两个项目。现在给你两个长度一样的数组,starts数组代码每个会议开始的时间,ends数组代表每个会议结束的时间。 在给你一个当前时间,请你求出当日可以利用会议室宣讲的…...
单日 5000 亿行 / 900G 数据接入,TDengine 3.0 在中国地震台网中心的大型应用
小T导读:为满足地震预警数据存储、检索和处理的建设与集成需求,以及响应国家国产软件自主可控的号召,中国地震台网中心决定选用国产数据库 TDengine 来存储和处理地震波形数据。本文将针对 TDengine 3.0 在地震领域的应用展开详细讲解。 关于…...
【VIM系列】cscope命令
cscope...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
SpringTask-03.入门案例
一.入门案例 启动类: package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
