iOS object-C 解答算法:找到所有数组中消失的数字(leetCode-448)

找到所有数组中消失的数字(leetCode-448)

题目如下图:(也可以到leetCode上看完整题目,题号448)

光看题看可能有点难以理解,我们结合示例1来理解一下这道题.

有8个整数的数组 nums = [4,3,2,7,8,2,3,1], 求在闭区间[1,8]范围内(即1,2,3,4,5,6,7,8)的数字,哪几个没有出现在数组 nums 中. 

我们很容易一看就看出,5和6没有出现在数组nums中.

还是拿示例1来说,如果可以用新建一个数组newNums = [1,2,3,4,5,6,7,8] 与 原数组nums = [4,3,2,7,8,2,3,1] 比较,立马可以找到缺少了元素5和6,但是题目要求不得使用额外空间.所以只能在原数组上操作.

解法一:

我们先来说一下常规解法(就是可以使用额外空间的解法). 遍历nums数组,把遍历到的元素一一在newNums数组里删除,剩下没删除的元素就是nunms没有的.

代码如下:

- (void)viewDidLoad 
{[super viewDidLoad];NSMutableArray * originalArray = [[NSMutableArray alloc]initWithObjects:@"4",@"3",@"2",@"7",@"8",@"2",@"3",@"1", nil];NSMutableArray * newArray = [[NSMutableArray alloc]init];for (int i = 1; i < originalArray.count + 1; i ++){[newArray addObject:[NSString stringWithFormat:@"%d",i]];}NSMutableArray * array2 = [self missNum:originalArray NewArray:newArray];NSLog(@"array2==%@",array2);
}- (NSMutableArray *)missNum:(NSMutableArray *)originalArray NewArray:(NSMutableArray *)newArray
{for (int i = 0 ; i < originalArray.count; i ++){NSString * oValue = originalArray[i];[newArray removeObject:oValue];}return newArray;
}

以上就是我们通常想到的常规解法,时间复杂度为O(n^2),空间复杂度为O(n). 

时间复杂度不符合题目要求的O(n), 题目还说了不占用额外空间(返回函数不算),这一点我不太懂,这一道题我开辟了很多空间,除了不算的返回函数newArray,还有int i, NSString * oValue, 这个算不算额外空间,如果有懂的小伙伴评论区帮我解答一下.

但是通常都是用空间换时间,所以这么写现实中问题不大.

解法二:

我们可以把 数组nums = [4,3,2,7,8,2,3,1] 看做是 数组newNums = [1,2,3,4,5,6,7,8],减去几个数,再增加几个相同的数(例如这里增加了2和3),再打乱它们的排列组合. 注意:nums和newNums的元素个数(就是count一定是相等的,这是题目隐含的意思).

所以在nums 里的index=0的元素4, 它原来的index应该为3. 我们就按照这个逻辑,把nums里所有元素的的原index都找到,那么剩下的没有找到的index,就是没有出现在nums 里的元素.

思路如下:

nums元素 4---->index = 3

nums元素 3---->index = 2

nums元素 2---->index = 1

nums元素 7---->index = 6

nums元素 8---->index = 7

nums元素 2---->index = 1

nums元素 3---->index = 2

nums元素 1---->index = 0

通过上面列出的思路,我们可以看到,index=4和index=5 没有出现,所以没有出现的数字为 5 和 6.

因为不能额外增加空间,所以我们不能新创建一个数组和存放index.那么我们只能使用标记法-->在原数组标记.

标记的方法有很多种,例如可以在数组前加个减号(-)标记, 也可以每个元素加上n标记(例如4+8),也可以使用符号标志(例如*,但是这道题是数字,明显不能用这个方法).

我们这里就使用减号标志号了

nums元素 4 ---> index = 3 ,在数组nums index=3的位置加个减号:nums = [4,3,2,-7,8,2,3,1];

nums元素 3 ---> index = 2 ,在数组nums index=2的位置加个减号:nums = [4,3,-2,-7,8,2,3,1];

nums元素 2 ---> index = 1 ,在数组nums index=1的位置加个减号:nums = [4,-3,-2,-7,8,2,3,1];

我们下一步按理说是要取元素7的,但是nums里7 已经变成-7了,所以我们为了不受标记影响,我们每次都取元素的绝对值(object-c取数字绝对值的方法为abs())

nums元素 7 ---> index = 6 ,在数组nums index=6的位置加个减号:nums = [4,-3,-2,-7,8,2,-3,1];

nums元素 8 ---> index = 7 ,在数组nums index=7的位置加个减号:nums = [4,-3,-2,-7,8,2,-3,-1];

下一步的元素2.index=1 的位置已经标记了减号,所以我么标记之前先判断待标记的位置是否为负数,如果为负数,则无需重复标记

nums元素 2 ---> index = 1 ,无需重复标记

nums元素 3 ---> index = 2 ,无需重复标记

nums元素 1 ---> index = 0,在数组nums index=0的位置加个减号:nums = [-4,-3,-2,-7,8,2,-3,-1];

经过一个for循环的标记,我们就找出数组里为正数数的index,即得到没有出现的数字

代码如下:

- (NSMutableArray *)missNum2:(NSMutableArray *)originalArray
{for (int i = 0 ; i < originalArray.count; i ++){//1.取值要取绝对值 abs()int value = abs([originalArray[i] intValue]);//2.获得元素的indexint index = value - 1;//3.标记index//3.1.标记之前要判断index的元素是否为负数,如果为负数,则说明已经标记过了,无需标记if (originalArray[index] > 0){originalArray[index] = [NSString stringWithFormat:@"-%@",originalArray[index]];}NSLog(@"originalArray==%@",originalArray);}NSMutableArray * newArray = [[NSMutableArray alloc]init];for (int i = 1; i < originalArray.count + 1; i ++){[newArray addObject:[NSString stringWithFormat:@"%d",i]];}return newArray;
}

以上代码的时间复杂度为O(n),空间复杂度也为O(n)

时间复杂度满足题目要求, 这个写法我也开辟了很多空间,除了不算的返回函数newArray,还有int value, int index , int i, 这个算不算额外空间,如果有懂的小伙伴评论区帮我解答一下.

​​​​​​​但是通常都是用空间换时间,所以这么写现实中问题不大.

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

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

相关文章

新装centos7虚拟机如何配置网络,NAT配置固定IP

首先声明&#xff0c;我想使用的是NAT连接模式&#xff0c;并且设置完IP之后&#xff0c;使得这个IP固定住&#xff0c;以后不会再变了。 文章目录 1&#xff0c;打开Vmware软件的【编辑】-【虚拟网络编辑器】2&#xff0c;先选择VMnet8&#xff08;画1处&#xff09;&#xf…

解析capl文件生成XML Test Module对应的xml工具

之前一直用的CAPL Test Module来写代码&#xff0c;所有的控制都是在MainTest()函数来实现的&#xff0c;但是有一次&#xff0c;代码都写完了&#xff0c;突然需要用xml的这种方式来实现&#xff0c;很突然&#xff0c;之前也没研究过&#xff0c;整理这个xml整的一身汗&#…

Hive3:库操作常用语句

1、创建库 create database if not exists myhive;2、选择库 use myhive;3、查看当前选择的库 SELECT current_database();4、查看库详细信息 desc database myhive;可以查看数据文件在hdfs集群中的存储位置 5、创建库时制定hdfs的存储位置 create database myhive2 …

安全防护软件的必要性:从微软蓝屏事件谈起

最近微软遭遇了的大规模蓝屏事件&#xff0c;让全球很多用户措手不及。这次事件告诉我们&#xff0c;保护我们的电脑和数据&#xff0c;安全防护软件是多么重要。 微软蓝屏事件源于网络安全公司CrowdStrike的技术更新错误&#xff0c;导致全球范围内大量Windows用户系统崩溃&a…

什么是五力分析?5分钟带你了解它在企业财务经营中的应用与价值!

如今&#xff0c;随着全球化进程的不断加速&#xff0c;市场环境复杂多变&#xff0c;市场竞争日益激烈&#xff0c;财务经营已经成为了企业应对复杂市场环境、保持自身竞争力的关键。体系化的五力分析平台能够为企业提供一套全面的解决方案&#xff0c;帮助企业在盈利能力、偿…

HamonyOS性能优化工具和方法

性能优化&#xff0c;如何做到更快的启动、更流畅的使用&#xff0c;概括图如下 ArkTS高性能编程&#xff1a; 1. ArkTS规则&#xff1a;有利于方舟编译运行时进行编译优化 2. 使用AOT(Ahead Of Time)模式对应用进行编译优化&#xff1a;方舟编译运行时通过采用PGO(Profile-Gui…

React 学习——组件内通信(兄弟之间)

A组件 > B组件 核心思路&#xff1a; 1、A组件先通过子传父的方式把数据传给父组件App 2、App拿到数据后通过父传子的方式再传递给B组件 import { useState } from "react" function A({onGetMsg}){const AMsg 我是A组件的消息return (<div><button…

ESP-ADF适配到自定义开发板中

ESP-ADF适配到自定义开发板中 前言:项目开发完了,来记录一下开发过程。 安装: 这里采用vscode+ESP-IDF+ESP-ADF的开发方式。 安装esp-idf的方法很简单,网上都是,这里不说了。想用esp-adf那么你idf的环境肯定是已经搭建好了。 安装adf也很简单,一步完成。 按下F1,选…

鸿蒙对接极光推送时候报错1000900010,厂商token获取失败

在AppGallery Connect上配置项目的调试证书&#xff0c;然后手动导入&#xff0c;不要用IDE的自动构建证书&#xff1a; https://developer.huawei.com/consumer/cn/service/josp/agc/index.html#/

web前端开发一、VScode环境搭建

1、VScode安装live server插件&#xff0c;写完代码后&#xff0c;保存就会在浏览器自动更新&#xff0c;不需要再去浏览器点击刷新了 2、创建html文件 3、在文件中输入感叹号 &#xff01; 4、选择第一个&#xff0c;然后回车&#xff0c;就会自动输入html的标准程序 5、…

js_拳皇(下)

文章目录 架构设计视频演示碰撞检测碰撞检测函数 构想血条和计时器全屏后续工作 架构设计 一图胜千言 #mermaid-svg-erOUDyAO5t0XgYyU {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-erOUDyAO5t0XgYyU .error-icon{…

微信聊天记录丢失怎么办?3款数据恢复大师免费版,你选对了吗?

在这个网络时代&#xff0c;微信可不只是用来聊天的&#xff0c;它还帮我们处理工作、记录生活、保存美好回忆。但是&#xff0c;如果微信里的东西突然没了&#xff0c;那感觉就像是回到了没有网络的黑暗时期&#xff0c;让人焦虑又无助。别怕&#xff0c;今天咱们就来说说大家…

整箱排柜不返工?用易境通散拼系统就OK

想必困扰散货拼柜小伙伴们一大难题就是&#xff0c;怎么把错乱纷繁的货物有序地整箱排柜&#xff0c;并且要保证集装箱高效利用&#xff0c;运输成本尽量降低。这不仅要求操作者具备卓越的统筹规划能力&#xff0c;更需长期积累的实践经验和敏锐的应变能力。易境通散拼系统可以…

HarmonyOS NEXT星河版零基础入门到实战

文章目录 一、HarmonyOS NEXT介绍学习内容1、鸿蒙APP开发2、能力套件开发3、全场景开发适合人群 持续更新中✒️总结 一、HarmonyOS NEXT介绍 放弃安卓框架之后&#xff0c;HarmonyOS NEXT成为真正独立于安卓、iOS的操作系统&#xff0c;堪称是一场史无前例的脱胎换骨。在其众多…

NC 缺失的第一个正整数

系列文章目录 文章目录 系列文章目录前言 前言 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站&#xff0c;这篇文章男女通用&#xff0c;看懂了就去分享给你的码吧。 描述 给定一个无重…

Python | Leetcode Python题解之第300题最长递增子序列

题目&#xff1a; 题解&#xff1a; class Solution:def lengthOfLIS(self, nums: List[int]) -> int:d []for n in nums:if not d or n > d[-1]:d.append(n)else:l, r 0, len(d) - 1loc rwhile l < r:mid (l r) // 2if d[mid] > n:loc midr mid - 1else:l…

6 Java的基本程序设计结构(基本语法5)- 面向对象进阶

文章目录 面向对象进阶一、 static 静态1 静态变量(1)基本定义和用法(2)静态变量内存图2 静态方法(1)基本定义和用法(2)工具类练习:按下面需求写一个工具类3 static注意事项4 重新认识main方法二、继承1 继承的概念2 继承的特点3 继承到底能继承父类中的哪些内容?4 继…

阿里云服务器 Ubuntu18.04 安装 mysql8.0并允许外部连接

参考教程&#xff1a; 官网教程 参考教程一 首先彻底删除mysql5.7 dpkg --list|grep mysql #查看 sudo apt-get remove mysql-common #卸载 sudo apt-get autoremove --purge mysql-server-5.7 #版本自己修改 dpkg -l|grep ^rc|awk {print$2}|sudo xargs dpkg -P #清除残留数…

【释放品牌魅力,开启营销新篇章】—— 短视频矩阵营销系统源码

【释放品牌魅力&#xff0c;开启营销新篇章】—— 短视频矩阵营销系统在这个数字化高速发展的时代&#xff0c;您是否还在为品牌曝光度不足、营销效果不佳而苦恼&#xff1f;来吧&#xff0c;让我们一起探索全新的解决方案——短视频矩阵营销系统&#xff01; 在这个数字化高速…

linux:基本权限

1、权限与用户之间的关系 在Linux系统中&#xff0c;针对文件定义了三种身份&#xff0c;分别是属主(owner)、属组(group)、其他人(others)&#xff0c;每一种身份又对应三种权限&#xff0c;分别是可读(readable)、可写(writable)、可执行(excutable)。 2、如何修改一个文件的…