在 Leetcode 上使用 Javascript 查找数组中的所有重复项(使用 JS 的 DSA)

在本篇博客文章中,我们将探讨如何在数组中找出所有重复的元素,这个问题源自LeetCode上的一个问题。
在这里插入图片描述

问题描述

我们有一个包含n个整数的数组,所有整数都在范围[1, n]内。每个整数要么出现一次,要么出现两次。任务是找出并返回一个包含所有出现两次的整数的数组。
要求算法的时间复杂度为O(n),并且只能使用固定的额外空间。

示例

Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:
Input: nums = [1,1,2]
Output: [1]

Example 3:
Input: nums = [1]
Output: []

这些示例展示了不同情况下的输入数组和对应的输出结果。

解题方法

考虑到数组中的整数范围是[1, n],其中n是数组的长度。这意味着最小的值是1,最大的值是n。例如,在第一个示例中,最小的数字是1,最大的数字是8,这也正好是数组的长度。

我们可以利用这个范围的特性来帮助我们解决问题。同时,我们知道数组的索引范围是[0, n-1]。

这意味着我们可以用数组中的每个值i - 1作为索引来访问数组。

以第一个示例数组[4,3,2,7,8,2,3,1]为例:

  • 对于第一个元素4,我们可以用4 - 1即索引3来访问数组。该索引处的值是7。我们可以将这个索引处的值变为负数,以此来标记这个值已经被访问过。
  • 用相同的方法处理第二个元素3,我们用3 - 1即索引2来访问数组。该索引处的值是2。我们将这个数字变为负数,以此标记。
  • 通过这种方式,如果一个索引的值是负数,那么表示对应的数字是重复的。

在示例中,数字3是重复的。在这两种情况下,它们都会指向相同的索引2。因此,我们可以将3添加到输出数组中。

为了更好地理解这个问题,建议查看相关的视频解释。

伪代码

创建一个空数组 output

循环遍历 nums:
    获取当前数字的绝对值
    获取当前数字的索引并减去1
    在索引处获取值
    如果索引处的值为负,
        将当前数字添加到输出数组
    否则:
        将索引处的值变为负

返回输出数组

代码实现(JavaScript):

var findDuplicates = function (nums) {
    const output = []

    nums.forEach(num => {
        const curr = Math.abs(num)
        const index = curr - 1
        const indexedValue = nums[index]

        if (indexedValue < 0) {
            output.push(curr)
        } else {
            nums[index] = indexedValue * -1
        }
    })

    return output
}

这就是解决问题的基本思路和方法。通过这种方式,我们可以有效地找出数组中所有重复的元素。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/536165.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

第8章 项目整合管理

子过程&#xff1a;为创建预定的产品、服务或成果而执行的一系列相互关联的行动和活动&#xff1b; 既属于某一过程组&#xff08;启动、规划、执行、监控、收尾&#xff09;又属于某一知识领域&#xff08;整合、范围、进度、成本、质量、资源、采购、沟通、干系人、风险&…

5G智慧水利数字孪生可视化平台,推进水利行业数字化转型

5G智慧水利数字孪生可视化平台&#xff0c;推进水利行业数字化转型。随着5G技术的快速发展&#xff0c;越来越多的行业开始探索数字化转型的道路。水利行业作为国民经济的重要支柱&#xff0c;也面临着数字化转型的迫切需求。5G智慧水利数字孪生可视化平台作为水利行业数字化转…

数据安全之路:Databend 用户与角色管理应用

Databend 目前支持基于角色的访问控制 (RBAC) 和 自主访问控制 (DAC) 模型&#xff0c;用于访问控制功能。 通过本指南&#xff0c;我们会了解权限和角色在 Databend 中的基本概念&#xff0c;以及如何管理角色、继承角色与建立层级、设置默认角色以及所有权的重要性。这些功能…

活动预告|NineData 创始人CEO叶正盛将参加QCon全球软件开发大会,共话AI大模型技术在数据库DevOps的实践

4月13日下午&#xff0c;NineData创始人&CEO叶正盛即将参加InfoQ中国主办的『QCon全球软件开发大会北京站』的技术大会。在本次技术峰会上&#xff0c;叶正盛将以《AI大模型技术在数据库DevOps的实践》为主题&#xff0c;深入剖析AI大模型技术在数据库DevOps领域的最新进展…

逆向案例二十一——遇到混淆怎么办

开始新的板块尝试&#xff0c;混淆了怎么办 网址&#xff1a;极简壁纸_海量电脑桌面壁纸美图_4K超高清_最潮壁纸网站 抓包抓到&#xff0c;好久没做解密了&#xff0c;奥里给干他&#xff01;&#xff1a; 搜索关键字&#xff0c;打上断点&#xff0c;点击第二页。 _0x10a345…

SOLIDOWRKS怎么将中间格式的模具装配体转化为装配体格式

模具是工业生产中用于制作成型物品的工具&#xff0c;它由各种零件构成&#xff0c;可以通过改变所成型材料的物理状态来实现物品外形的加工。如果工程师已经有其他格式的模具装配体&#xff0c;但是又想将其他格式的模具装配体导入solidworks里面&#xff0c;并且将一个个实体…

rust wasm入门

&#x1f4d5;作者简介&#xff1a; 过去日记&#xff0c;致力于Java、GoLang,Rust等多种编程语言&#xff0c;热爱技术&#xff0c;喜欢游戏的博主。 &#x1f4d8;相关专栏Rust初阶教程、go语言基础系列、spring教程等&#xff0c;大家有兴趣的可以看一看 &#x1f4d9;Jav…

SpringBoot修改菜品模块开发

需求分析与设计 一&#xff1a;产品原型 在菜品管理列表页面点击修改按钮&#xff0c;跳转到修改菜品页面&#xff0c;在修改页面回显菜品相关信息并进行修改&#xff0c;最后点击保存按钮完成修改操作。 修改菜品原型&#xff1a; 二&#xff1a;接口设计 通过对上述原型图…

图像处理与视觉感知---期末复习重点(7)

文章目录 一、图像压缩1.1 三种冗余1.2 模型1.3 信息测量 二、无误差压缩2.1 哈夫曼编码2.1.1 步骤2.1.2 例题 2.2 算术编码 三、变换编码 一、图像压缩 1.1 三种冗余 1. 三种基本的是数据冗余为&#xff1a;编码冗余、像素间冗余、心理视觉冗余。 2. 编码冗余&#xff1a;如果…

在线拍卖系统|基于Springboot的在线拍卖系统设计与实现(源码+数据库+文档)

在线拍卖系统目录 基于Springboot的在线拍卖系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、前台&#xff1a; 2、后台 用户功能模块 5.2用户功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a…

个人博客系统项目(SpringBoot+Linux部署上线)

在学完SpringBoot框架、MyBatis后&#xff0c;直接开始做第一个项目&#xff1a;博客系统 首先&#xff0c;该博客系统包含核心功能有&#xff1a; 一、登录、注册、退出登录功能。 二、没有登陆前可以查看博客首页以及博客展示的分页处理&#xff0c;以及点击查看博客可以…

ELK-Kibana 部署

目录 一、在 node1 节点上操作 1.1.安装 Kibana 1.2.设置 Kibana 的主配置文件 1.3.启动 Kibana 服务 1.4.验证 Kibana 1.5.将 Apache 服务器的日志&#xff08;访问的、错误的&#xff09;添加到 ES 并通过 Kibana 显示 1.6. 浏览器访问 二、部署FilebeatELK&…

牛客NC413 两个升序数组的中位数【hard 数组,模拟 Java、Go、PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/b3b59248e61f499482eaba636305474b 思路 直接模拟2个数组有顺序放到一个数组中help中如果help长度为奇数&#xff0c;返回中间的数如果help长度为偶数&#xff0c;返回中间2个数的和除以2参考答案java import j…

ES6 全详解 let 、 const 、解构赋值、剩余运算符、函数默认参数、扩展运算符、箭头函数、新增方法,promise、Set、class等等

目录 ES6概念ECMAScript6简介ECMAScript 和 JavaScript 的关系ES6 与 ECMAScript 2015 的关系 1、let 、 const 、var 区别2、变量解构赋值1、数组解构赋值2、对象解构赋值3、字符串的解构赋值 3、展开剩余运算符1、**展开运算符(...)**2、**剩余运算符(...)** 4、函数的拓展函…

JSONP是跨域资源共享的古老技术吗

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【MySQL】锁篇

SueWakeup 个人主页&#xff1a;SueWakeup 系列专栏&#xff1a;学习技术栈 个性签名&#xff1a;保留赤子之心也许是种幸运吧 本文封面由 凯楠&#x1f4f8;友情提供 目录 本系列专栏 1. MySQ 中的锁 2. 表锁和行锁 表锁 行锁 3. InnoDB 存储引擎的三种行级锁 4. 悲观锁…

【腾讯云 TDSQL-C Serverless 产品体验】饮水机式使用云数据库

云计算的发展从IaaS&#xff0c;PaaS&#xff0c;SaaS&#xff0c;到最新的BaaS&#xff0c;FasS&#xff0c;在这个趋势中serverless(去服务器化&#xff09; 计算资源发展Physical -> Virtualisation -> Cloud Compute -> Container -> Serverless。 一、背景介绍…

21、矩阵-搜索二维矩阵

思路&#xff1a; 这道题很有意思 从左到有升序&#xff0c;从上到下升序&#xff0c;斜边从左上到右下也是升序&#xff0c;从右上到做下降序。 如果是从左往右依次遍历&#xff0c;就会面临一个问题向右还是向下&#xff0c;因为都是大于当前值&#xff0c;不好决断&#x…

结合fastapi-users与Langserve轻松实现大语言接口用户认证

在做大模型开发的过程中&#xff0c;相信很多小伙伴都是对大模型开发感兴趣&#xff0c;却对 fastapi 这个框架并不熟悉&#xff0c;但是&#xff0c;实际开发的项目确需要用户鉴权&#xff0c;这时候就会很头疼&#xff0c;查阅官方文档发现&#xff0c;官方虽然有例子&#x…

软考123-上午题-【软件工程】-系统设计

一、系统设计 1-1、概要设计 设计软件系统总结结构数据结构及数据库设计编写概要设计文档评审 1-1-1、设计软件系统总结结构 其基本任务是采用某种设计方法&#xff0c;将一个复杂的系统按功能划分成模块&#xff1b; 确定每个模块的功能&#xff1b;确定模块之间的调用关系…