news 2026/1/26 13:35:22

力扣刷题:数组中重复的数据

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
力扣刷题:数组中重复的数据

题目:
给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 最多两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间(不包括存储输出所需的空间)的算法解决此问题。

示例 1:

输入:nums = [4,3,2,7,8,2,3,1]
输出:[2,3]

示例 2:

输入:nums = [1,1,2]
输出:[1]

示例 3:

输入:nums = [1]
输出:[]

解析:
这道题的思想是原地哈希,因为题目中比较特殊,数组中每一个数的值是在[1,n]这个区间中,数组的长度也刚好为n,所以我们可以借助数组中某个数的前一个索引表示这个数是否出现过,如果没出现过,就将这个数减一作为下标对应的元素设置为负数。
举个例子:
比如数组有个元素为4,那么我们将arr[4-1]对应的那个元素乘以-1,变为负数,那么下次我们再次遇到4这个数的时候,我们去查看arr[4-1]对应的元素,如果对应的元素为负数,那么说明元素4之前出现过一次

具体代码:

/** * 找出数组中所有出现两次的元素(LeetCode 442题) * 条件:1 ≤ nums[i] ≤ n,n为数组长度,每个元素最多出现两次 * @param {number[]} nums - 输入数组,元素值在[1, n]范围内 * @return {number[]} - 返回所有出现两次的元素 */varfindDuplicates=function(nums){// 存储结果的数组letres=[]// 遍历数组中的每个元素for(leti=0;i<nums.length;i++){// 取当前元素的绝对值(因为可能已经被标记为负数)letk=Math.abs(nums[i])// 检查 nums[k-1] 这个位置的值:// - 如果 nums[k-1] > 0:说明数字 k 是第一次出现// - 如果 nums[k-1] < 0:说明数字 k 之前已经出现过一次,现在是第二次出现// 核心思路:用索引 (k-1) 位置的符号来标记数字 k 是否出现过if(nums[k-1]>0){// 第一次遇到数字 k:将 nums[k-1] 标记为负数// 负号作为"已访问"标记,不影响我们通过 Math.abs 获取原始值nums[k-1]*=-1}else{// 第二次遇到数字 k:当前 nums[k-1] 已经是负数// 说明 k 是重复元素,将其加入结果数组res.push(k)}}// 返回所有出现两次的元素returnres};
版权声明: 本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!
网站建设 2026/1/24 22:02:08

equals与==区别

equals与区别 章节目录 文章目录equals与区别在Java中&#xff0c;""是一个比较操作符&#xff0c;用于比较两个变量的值是否相等。而"equals()"是Object类中定义的方法&#xff0c;用于比较两个对象是否相等。""用于比较基本数据类型和引用类型…

作者头像 李华
网站建设 2026/1/21 10:17:11

HitPaw水印去除器V1.2.1.1:终极图片视频去水印完整指南

HitPaw水印去除器V1.2.1.1&#xff1a;终极图片视频去水印完整指南 【免费下载链接】HitPawWatermarkRemover官方中文版V1.2.1.1详细介绍 HitPaw Watermark Remover是一款功能强大的去水印工具&#xff0c;专注于为用户提供高效、专业的图片和视频水印清除解决方案。通过先进的…

作者头像 李华
网站建设 2026/1/20 23:23:47

PyZh项目:Python技术文档的协同翻译平台

PyZh项目&#xff1a;Python技术文档的协同翻译平台 【免费下载链接】PyZh :books: 一起写Python文章&#xff0c;一起看Python文章 - 利用readthedocs的Python技术文章的收集和翻译。 项目地址: https://gitcode.com/gh_mirrors/py/PyZh PyZh是一个专注于Python技术文档…

作者头像 李华
网站建设 2026/1/18 14:23:04

企业级AI落地首选:TensorFlow生产部署最佳实践

企业级AI落地首选&#xff1a;TensorFlow生产部署最佳实践 在金融风控系统突然出现误判、推荐引擎响应延迟飙升到数百毫秒的那一刻&#xff0c;很多企业的AI团队才真正意识到&#xff1a;实验室里跑通的模型&#xff0c;离稳定上线还差得远。这不仅是算法问题&#xff0c;更是一…

作者头像 李华
网站建设 2026/1/26 7:57:16

Subnautica Nitrox多人联机模组:终极协作探险完整指南

Subnautica Nitrox多人联机模组&#xff1a;终极协作探险完整指南 【免费下载链接】Nitrox An open-source, multiplayer modification for the game Subnautica. 项目地址: https://gitcode.com/gh_mirrors/ni/Nitrox 你是否曾幻想与挚友并肩潜入《深海迷航》的未知深渊…

作者头像 李华
网站建设 2025/12/27 10:55:38

TensorFlow镜像下载加速:提升GPU算力利用率的秘诀

TensorFlow镜像下载加速&#xff1a;提升GPU算力利用率的秘诀 在AI研发节奏日益加快的今天&#xff0c;一个看似不起眼的操作——拉取TensorFlow容器镜像——却可能成为压垮GPU资源利用率的“最后一根稻草”。你是否经历过这样的场景&#xff1a;刚申请到一台昂贵的A100实例&am…

作者头像 李华