【第0007页 · 数组】数组中重复的数据(如何实现数组的原地修改)

【前言】本文以及之后的一些题解都会陆续整理到目录中,若想了解全部题解整理,请看这里:

第0007页 · 数组中重复的数据

        今天,我们来看一个在实际工作中运用不多,但是对于一些算法题还是有必要的奇技淫巧——数组的原地修改。下面我们将通过两道题目来学习这种技巧。

【找到所有数组中消失的数】 给你一个含 n 个整数的数组 nums ,其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字,并以数组的形式返回结果。

示例1示例2
输入描述:nums = [4, 3, 2, 7, 8, 2, 3,1]输入描述:nums = [1, 1]
输出描述:[5, 6]输出描述:[2]

【解题分析】这道题本来十分简单,但是如果加上一个要求:在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 可以假定返回的数组不算在额外空间内。那么这道题就有些内容可以说了。

        这里我们先来讲解一下这种原地修改的想法:首先,由于 nums 的长度恰好为 n,而我们要查找的数字范围均在 [1, n] 中,那么我们不妨将位置 k 处的值当成数字 k + 1 是否出现的凭证。以上是 Hash 的思想。

        接下来,我们需要考虑如何才能使位置 k 处的值能够代表数字 k + 1 是否出现过。我们提供一种想法是如果 k + 1 出现过,需要将位置 k 处的值加上 n,因为本来数组中所有的数都小于 n,只能是由于出现过而导致大于 n。根据以上想法,我们就可以使位置 k 处的值能够代表数字 k + 1 是否出现过。

【源码展示】

class Solution {
public:vector<int> findDisappearedNumbers(vector<int>& nums) {int n = nums.size();for (int num : nums) {int x = (num - 1) % n;nums[x] += n;}vector<int> ret;for (int i = 0; i < n; i++) {if (nums[i] <= n) {ret.push_back(i + 1);}}return ret;}
};

         解决完上面这道题,我们再来看今天的第二题,中间也需要用到类似的思想。

【数组中重复的数据】给你一个长度为 n 的整数数组 nums ,其中 nums 的所有整数都在范围 [1, n] 内,且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数,并以数组形式返回。

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

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

【解题分析】这里和上面一题的要求几乎一致,思路也差不多,就留给读者自行思考了

【源码展示】

class Solution {
public:vector<int> findDuplicates(vector<int>& nums) {int size = nums.size();for (int i = 0; i< size; i++) {// Swap until appear in right poswhile (nums[i] != nums[nums[i] - 1]) {swap(nums[i], nums[nums[i] - 1]);}}vector<int> ans;for (int i = 0; i < size; i++) {if (nums[i] != (i+1)) {ans.emplace_back(nums[i]);}}return ans;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

探索非局部均值滤波在椒盐噪声去除中的应用

在图像处理领域&#xff0c;椒盐噪声是一种常见的干扰&#xff0c;它会导致图像出现随机的黑白像素点&#xff0c;严重影响图像质量。为了解决这一问题&#xff0c;本文将介绍一种有效的去噪技术——非局部均值滤波&#xff08;NLM&#xff09;的改进版本&#xff0c;即NAMF&am…

springboot数据库连接由localhost改成IP以后访问报错500(2024/9/7

步骤很详细&#xff0c;直接上教程 情景复现 一.没改为IP之前正常 二.改完之后报错 问题分析 SQL没开启远程连接权限 解决方法 命令行登入数据库 mysql -u root -p切换到对应数据库 use mysql;设置root用户的连接权限允许其他IP连接数据库 update user set host % whe…

keepalived和lvs高可用集群

keepavlied和lvs高可用集群搭建 主备模式&#xff1a; 关闭防火墙和selinux systemctl stop firewalld setenforce 0部署master负载调度服务器 zyj86 安装ipvsadm keepalived yum install -y keepalived ipvsadm修改主节点配置 vim /etc/keepalived/keepalived.conf! Conf…

240908-Linux设置软连接关联大模型文件

在Linux中&#xff0c;您可以使用ln命令来创建软链接&#xff08;符号链接&#xff09;。软链接是一种特殊类型的文件&#xff0c;它指向另一个文件或目录。以下是如何设置软链接的步骤&#xff1a; 创建软链接 基本语法&#xff1a; ln -s [目标文件或目录] [软链接的名称]示…

驾驭不断发展的人工智能世界

从很多方面来看&#xff0c;历史似乎正在重演。许多企业正争相采用生成式人工智能 (Gen AI)&#xff0c;就像它们争相采用云计算一样&#xff0c;原因也是一样的&#xff1a;效率、成本节约和竞争优势。 然而&#xff0c;与云一样&#xff0c;GenAI 仍是一项发展中的技术&…

Django+Vue3前后端分离学习(一)(项目开始时settings.py里的设置)

一、创建django项目 二、修改settings.py里的配置&#xff1a; 1、修改语言和时区&#xff1a; # 语言编码 LANGUAGE_CODE zh-hansTIME_ZONE UTCUSE_I18N True# 不用时区 USE_TZ False 2、配置数据库&#xff1a; DATABASES {default: {ENGINE: django.db.backends.m…

[数据集][目标检测]街头摊贩识别检测数据集VOC+YOLO格式758张1类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;758 标注数量(xml文件个数)&#xff1a;758 标注数量(txt文件个数)&#xff1a;758 标注类别…

前端几种常见框架【第一节】

​ 大家好&#xff0c;我是程序员小羊&#xff01; 前言&#xff1a; 最近比较忙&#xff0c;本人在复习软考中级设计考试&#xff0c;所以本系列文从零基础开始复习软考到结束软考&#xff08;计算机技术与软件专业技术资格考试&#xff09;作为国家级职业资格认证考试&#x…

【路径规划】 使用计算机视觉和机器人操纵器绘制肖像

摘要 本项目展示了使用计算机视觉和机械臂绘制肖像的完整流程。系统利用网络摄像头获取肖像图像&#xff0c;经过图像处理后生成路径&#xff0c;然后利用逆向运动学将路径转化为机械臂的运动轨迹&#xff0c;最终在硬件机器人上执行绘制。实验结果表明&#xff0c;该系统能够…

Android Launcher3

一、定义与功能 Android Launcher是Android操作系统中的一个重要组件&#xff0c;它负责管理和呈现用户界面&#xff0c;包括桌面、应用程序抽屉和部件。Launcher不仅为用户提供了一个启动应用程序的入口&#xff0c;还允许用户自定义手机的主屏幕、图标、小部件布局以及一些基…

2023年AI芯片峰会

概述 开幕式 再谈人工智能芯片——魏少军 可重构计算技术的软件定义芯片 生成式AI与大语言模型时代的NVIDIA GPU生态——NVIDIA NN的发展脉络 1989年&#xff0c;证明神经网络可以表示概率的近似&#xff0c;使得其具有强大的数据拟合能力。 模型的各项能力在2020年基本超…

u盘显示需要格式化才能用预警下的数据拯救恢复指南

U盘困境&#xff1a;需要格式化的紧急应对 在数字信息爆炸的时代&#xff0c;U盘作为便携的数据存储介质&#xff0c;承载着我们工作、学习乃至生活中的大量重要资料。然而&#xff0c;当U盘突然弹出“需要格式化才能用”的提示时&#xff0c;这份便捷瞬间转化为焦虑与不安。这…

Java架构师未来篇大模型

目录 1. 大模型的定义2 大模型相关概念区分3 大模型的发展历程4. 大模型的特点5 大模型的分类6 大模型的泛化与微调7 大模型岗位需求8 理解大模型8.1 生活中的比喻8.2 大模型的定义9 大模型工作9.1 数据的积累9.2 模型的训练9.3 预测和应用10 大模型的实际应用10.1 语言处理10.…

Ai+若依(智能售货机运营管理系统---帝可得)-人员管理-点位管理-区域管理-合作商管理----【08篇---0001:上】

项目介绍 售货机简介 帝可得是一个基于物联网概念下的智能售货机运营管理系统 物联网 物联网(IoT:Internet of Things)简单来说,就是让各种物品通过互联网连接起来,实现信息的交换和通信。 这个概念听起来可能有点抽象,但我们可以把它想象成一个超级大的社交网络。不过…

Java 日志

日志就是为了将程序的运行状况保存到文件中去。 命名的一个小细节&#xff1a; 比如把信息保存到文件中这个方法的名字可以写为infoToFile&#xff0c;有个人为了偷懒&#xff0c;写成info2File&#xff0c;发现效果还挺好&#xff0c;一下就能分清两个单词&#xff0c;所以后…

Cmake之3.0版本重要特性及用法实例(十三)

简介&#xff1a; CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布&#xff1a;《Android系统多媒体进阶实战》&#x1f680; 优质专栏&#xff1a; Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a; 多媒体系统工程师系列【…

Linux 安装nodejs环境

文章目录 Node.js简介Node.js的核心特性Node.js的生态系统Node.js的模块系统 部署下载Node.js预编译二进制包上传到Linux服务器并解压配置环境变量验证安装 部署在下边&#xff0c;我先对nodejs进行一些介绍&#xff0c;大家了解一下 Node.js简介 Node.js是一个基于Chrome V8…

2024国赛数学建模A题B题C题D题E题思路资料模型

开始在本帖实时更新2024国赛数学建模赛题思路代码&#xff0c;文章末尾获取&#xff01; 持续更新参考思路

港科夜闻 | 叶玉如校长出席2024科技+新质生产力高峰论坛发表专题演讲,贡献国家科技强国战略...

关注并星标 每周阅读港科夜闻 建立新视野 开启新思维 1、叶玉如校长出席“2024科技新质生产力高峰论坛”&#xff0c;做了题为“三个创新&#xff1a;培育和发展新质生产力、贡献国家科技强国战略”的主题演讲。该论坛于9月2日在香港召开。论坛围绕夯实基础科研、推动源头创新、…

OneHotEncoder一个不太合理的地方

OneHotEncoder&#xff0c;在Xtrain上fit&#xff0c;在Xtest上transform 如果遇到某个值出现在Xtest&#xff0c;而没有在Xtrain出现过时&#xff0c;会抛出如下错误&#xff1a; OneHotEncoder Found unknown categories [xxx] in column xx during transform OneHotEncoder …