当前位置:网站首页>笔试面试题目:求缺失的最小正整数
笔试面试题目:求缺失的最小正整数
2020-11-08 10:30:00 【osc_vuza8uho】
原文发表于:
国庆假期已过半。今天,我们来看一个leetcode问题,也是当年B公司的面试题,有难度。问题如下:
给定一个整数数组,找出其中缺失的最小的正整数,要求时间复杂度为O(n), 空间复杂度为O(1). 输入输出示例如下:
输入数组a | 输出 |
[1, 2, 0] | 3 |
[3, 4, 1, -1] | 2 |
[6, 7, 8, 12] | 1 |
我们先来分析一下:
A. 假设a中的n个元素占满了1~n, 那么缺失的最小正整数就是n+1.
B. 假设a中的n个元素没有完全占满1~n, 那么缺失的最小正整数必然是1~n之间的某个数。
综合A和B可知:缺失的最小正整数必然在区间[1, n+1]中。这是一个非常重要的结论。
算法1:暴力算法
暴力算法很简单,直接遍历区间[1, n+1], 然后判断元素是否在a中。此时,时间复杂度是O(n*n), 空间复杂度为O(1).
显然,无法通过面试。
算法2:哈希算法
从暴力算法可知,这无非就是一个查找的问题,那么可以考虑用哈希表。也就是把a数组用哈希表来记录,然后直接遍历区间[1, n+1], 就可以判断元素是否在哈希表中。此时,时间复杂度和空间复杂度都是O(n).
显然,无法通过面试。
算法3:巧妙标记法
我们参考算法2,并在标记元素是否存在时做巧妙优化。
以a = [3, 4, 1, -1]为例,n = 4,过程如下:
原始数组 | [3, 4, 1, -1] |
非正数改为n+1 | [3, 4, 1, 5] |
3存在,用a[3-1]的负号来标识 | [3, 4, -1, 5] |
4存在,用a[4-1]的负号来标识 | [3, 4, -1, -5] |
1存在,用a[1-1]的负号来标识 | [-3, 4, -1, -5] |
a[x-1]=4,是正数,故x必然不存在 | x=2便是缺失的最小正整数 |
可以看到,在记录元素x是否存在时,使用的是a[x - 1]的符号,其中,x的区间是[1, n]. 该算法的时间复杂度是O(n), 空间复杂度是O(1), 完全符合题目要求。 这种标记方式是非常巧妙的,而且确实不太容易想到。
既然算法的步骤确定了,那么对应的程序就相对简单了,来看一下:
package main
import "fmt"
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
func solution(a []int) int {
n := len(a)
for i := 0; i < n; i++ {
if a[i] <= 0 {
a[i] = n + 1
}
}
for i := 0; i < n; i++ {
num := abs(a[i])
if num <= n {
a[num - 1] = -abs(a[num - 1])
}
}
for i := 0; i < n; i++ {
if a[i] > 0 {
return i + 1
}
}
return n + 1
}
func main() {
a := []int{3, 4, 1, -1}
fmt.Println(solution(a))
}
结果:2
算法4:置换归位法
算法3是比较难想到的,那么我们再看看更加直观的想法。对于数组a的元素i, 如果i在区间[1, n]中,可通过置换归位,把i放到a[i-1]处,如下:
输入数组a | 置换目标 |
[1, 2, 0] | [1, 2, 0] |
[3, 4, 1, -1] | [1, -1, 3, 4] |
[6, 7, 8, 12] | [6, 7, 8, 12] |
置换后,再次遍历a, 如果a[x-1]和x不相等,那么,x肯定就是缺失的最小正整数,如下:
置换目标 | x(缺失的最小正整数) |
[1, 2, 0] | 3 |
[1, -1, 3, 4] | 2 |
[6, 7, 8, 12] | 1 |
该算法的时间复杂度是O(n), 空间复杂度是O(1), 完全符合题目要求。既然算法确定了,那么对应的程序就相对简单了,如下:
package main
import "fmt"
func solution(a []int) int {
n := len(a)
for i := 0; i < n; i++ {
// 注意:下面这里要用for, 而不是if.
for a[i] > 0 && a[i] <= n && a[a[i]-1] != a[i] {
a[a[i]-1], a[i] = a[i], a[a[i]-1]
}
}
for i := 0; i < n; i++ {
if a[i] != i + 1 {
return i + 1
}
}
return n + 1
}
func main() {
a := []int{3, 4, 1, -1}
fmt.Println(solution(a))
}
结果:2
综上所述:算法1和算法2无法通过面试,算法3和算法4可以通过面试。其中,算法3是比较绕的,在面试现场不太容易想到。相比较而言,算法4直观易懂,在程序实现时要注意内层要用for, 而不是if.
总体来看,B公司的面试要求还是很高的,祝大家拿到心仪的offer.
版权声明
本文为[osc_vuza8uho]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4290163/blog/4707997
边栏推荐
- Adobe Prelude /Pl 2020软件安装包(附安装教程)
- YGC troubleshooting, let me rise again!
- Rust: command line parameter and environment variable operation
- TCP协议如何确保可靠传输
- Face recognition: attack types and anti spoofing techniques
- Ulab 1.0.0 release
- Flink's sink: a preliminary study
- How does spotify drive data-driven decision making?
- 2天,利用下班后的4小时开发一个测试工具
- 双向LSTM在时间序列异常值检测的应用
猜你喜欢
【原创】关于高版本poi autoSizeColumn方法异常的情况
AMD Zen3首发评测:频率超5GHz,IPC提升不止19%,这次真的Yes了 - 知乎
Seven features of Python 3.9
Is there a big difference between i5 1135g7 and i51035g1? Which is better?
ts流中的pcr与pts计算与逆运算
Astra: Apache Cassandra的未来是云原生
Game optimization performance (11) - Zhihu
Cloud Alibabab笔记问世,全网详解仅此一份手慢无
Oschina plays on Sunday - before that, I always thought I was a
Deeplight Technology Bluetooth protocol SRRC certification services
随机推荐
软件测试培训班出来好找工作么
Visual Studio 2015 未响应/已停止工作的问题解决
2 days, using 4 hours after work to develop a test tool
211 postgraduate entrance examination failed, stay up for two months, get the byte offer! [face to face sharing]
SQL Server 2008R2 18456错误解决方案
The young generation of winner's programming life, the starting point of changing the world is hidden around
How TCP protocol ensures reliable transmission
不多不少,大学里必做的五件事(从我的大一说起)
Flink's sink: a preliminary study
“1024”征文活动结果新鲜出炉!快来看看是否榜上有名?~~
学习小结(关于深度学习、视觉和学习体会)
YGC troubleshooting, let me rise again!
Rust:命令行参数与环境变量操作
PCIe enumeration process
laravel8更新之速率限制改进
FORTRAN 77 reads some data from the file and uses the heron iteration formula to solve the problem
VC++指定目录下文件按时间排序输出
M-end software product design considerations - Zhihu
Mate 40 series launch with Huawei sports health service to bring healthy digital life
Adobe Prelude / PL 2020 software installation package (with installation tutorial)