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个丢失,找出丢失的数,如需转载请自行联系原博主。

相关文章
|
7月前
|
SQL 容灾 数据库管理
连续数据复制
连续数据复制
37 6
|
资源调度 流计算
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(下)
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(下)
159 1
|
2月前
3191. 使二进制数组全部等于 1 的最少操作次数 I 和3192. 使二进制数组全部等于 1 的最少操作次数 II
【10月更文挑战第2天】3191. 使二进制数组全部等于 1 的最少操作次数 I 和3192. 使二进制数组全部等于 1 的最少操作次数 II
15 0
|
5月前
|
域名解析 运维 Serverless
函数计算产品使用问题之设置最大实例数为1和最大并发数为20,当请求数量超过20时,系统会如何处理
阿里云Serverless 应用引擎(SAE)提供了完整的微服务应用生命周期管理能力,包括应用部署、服务治理、开发运维、资源管理等功能,并通过扩展功能支持多环境管理、API Gateway、事件驱动等高级应用场景,帮助企业快速构建、部署、运维和扩展微服务架构,实现Serverless化的应用部署与运维模式。以下是对SAE产品使用合集的概述,包括应用管理、服务治理、开发运维、资源管理等方面。
交换两个数的值的方法(三种)
交换两个数的值的方法(三种)
70 1
|
7月前
|
C++
丢失的数字(C++)
丢失的数字(C++)
60 0
|
监控 流计算
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(上)
Flink 指标参数源码解读(读取数量、发送数量、发送字节数、接收字节数等)(上)
97 1
|
监控 Shell
监控内存和磁盘容量,小于给定值时报警
监控内存和磁盘容量,小于给定值时报警
176 1
|
Shell Perl
查找 80 端口请求数最高的前 20 个 IP 地址,判断中间最小的请求数是否大于 500,如大于 500,则输出系统活动情况报告到 alert.txt,如果没有,则在 600s 后重试,直到有输出为止
查找 80 端口请求数最高的前 20 个 IP 地址,判断中间最小的请求数是否大于 500,如大于 500,则输出系统活动情况报告到 alert.txt,如果没有,则在 600s 后重试,直到有输出为止
103 1
1245:不重复地输出数 2020-12-28
1245:不重复地输出数 2020-12-28