1,2,...n n个数m个丢失,找出丢失的数

简介:

最简单的方法,开个O(n)的空间,扫描一遍,吧出现的数的记录下来。再扫描一下找出丢失的数字。时间复杂度O(n)

如果不允许开空间:可以排序,然后遍历一遍找出未出现的数。采用基数排序O(d*n),当n<=100000是复杂度 O(7*n)解决O(n),不过破坏了原来的数组

不破坏原来数组的方法:如果小于n个数补0 补成n个数。

扫描数组,if(a[i]>0)a[a[i]]+=2*n;再扫描一遍 if(a[i]<=n) cout<<i<< " ";else a[i] -= 2*n;//恢复数组

O(2*n),不破坏原数组。

本文转自博客园知识天地的博客,原文链接:1,2,...n n个数m个丢失,找出丢失的数,如需转载请自行联系原博主。

相关文章
|
资源调度 流计算
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(下)
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(下)
164 1
|
5月前
|
域名解析 运维 Serverless
函数计算产品使用问题之设置最大实例数为1和最大并发数为20,当请求数量超过20时,系统会如何处理
阿里云Serverless 应用引擎(SAE)提供了完整的微服务应用生命周期管理能力,包括应用部署、服务治理、开发运维、资源管理等功能,并通过扩展功能支持多环境管理、API Gateway、事件驱动等高级应用场景,帮助企业快速构建、部署、运维和扩展微服务架构,实现Serverless化的应用部署与运维模式。以下是对SAE产品使用合集的概述,包括应用管理、服务治理、开发运维、资源管理等方面。
|
7月前
1004.最大连续1的个数
1004.最大连续1的个数
35 0
|
监控 流计算
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(上)
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(上)
102 1
|
API 索引
主机磁盘使用率超过85%导致es索引变为只读模式
主机磁盘使用率超过85%导致es索引变为只读模式
425 0
|
监控 Shell
监控内存和磁盘容量,小于给定值时报警
监控内存和磁盘容量,小于给定值时报警
183 1
|
Python
一日一技:快速判断一个数属于等间隔范围中的位置
一日一技:快速判断一个数属于等间隔范围中的位置
102 0
寻找重复数
给定一个包含 n + 1 个整数的数组 nums ,其数字都在 [1, n] 范围内(包括 1 和 n),可知至少存在一个重复的整数。 假设 nums 只有 一个重复的整数 ,返回 这个重复的数 。 你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间
67 0