当前位置:网站首页>Written interview questions: find the smallest positive integer missing
Written interview questions: find the smallest positive integer missing
2020-11-08 10:30:00 【osc_redits】
Original published in :
The National Day holiday is over half . today , Let's take a look at one leetcode problem , It was the same year B Interview questions for the company , Difficult . Questions as follows :
Given an array of integers , Find the smallest missing positive integer , The required time complexity is O(n), The space complexity is O(1). The input and output examples are as follows :
Input array a | Output |
[1, 2, 0] | 3 |
[3, 4, 1, -1] | 2 |
[6, 7, 8, 12] | 1 |
Let's analyze first :
A. hypothesis a Medium n It's full of elements 1~n, Then the missing smallest positive integer is n+1.
B. hypothesis a Medium n The elements are not fully occupied 1~n, Then the missing smallest positive integer must be 1~n Some number between .
comprehensive A and B You know : The missing smallest positive integer must be in the interval [1, n+1] in . This is a very important conclusion .
Algorithm 1: The brute force algorithm
The brute force algorithm is simple , Traversing the interval directly [1, n+1], Then determine whether the element is in a in . here , The time complexity is O(n*n), The space complexity is O(1).
obviously , Can't pass the interview .
Algorithm 2: The hash algorithm
From the violence algorithm we can see that , It's nothing more than a search question , Then consider hash table . That is the a Arrays are recorded in hash tables , And then we traverse the interval directly [1, n+1], You can determine whether the element is in the hash table . here , Time complexity and space complexity are both O(n).
obviously , Can't pass the interview .
Algorithm 3: Clever marking
We refer to Algorithms 2, And make clever optimization when marking the existence of elements .
With a = [3, 4, 1, -1] For example ,n = 4, The process is as follows :
The original array | [3, 4, 1, -1] |
Change the non positive number to n+1 | [3, 4, 1, 5] |
3 There is , use a[3-1] The negative sign of | [3, 4, -1, 5] |
4 There is , use a[4-1] The negative sign of | [3, 4, -1, -5] |
1 There is , use a[1-1] The negative sign of | [-3, 4, -1, -5] |
a[x-1]=4, Positive number , so x There must not be | x=2 Is the missing smallest positive integer |
You can see , In the record element x If it exists , It uses a[x - 1] The symbol of , among ,x The interval of is [1, n]. The time complexity of the algorithm is O(n), The space complexity is O(1), It fully meets the requirements of the topic . This kind of marking is very clever , And it's really not easy to think of .
Now that the steps of the algorithm are determined , So the corresponding program is relatively simple , Take a look at :
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))
}
result :2
Algorithm 4: Displacement and homing
Algorithm 3 It's hard to think of , So let's look at more intuitive ideas . For arrays a The elements of i, If i In the interval [1, n] in , Can be returned by replacement , hold i Put it in a[i-1] It's about , as follows :
Input array a | Replace the goal |
[1, 2, 0] | [1, 2, 0] |
[3, 4, 1, -1] | [1, -1, 3, 4] |
[6, 7, 8, 12] | [6, 7, 8, 12] |
After replacement , Traverse... Again a, If a[x-1] and x It's not equal , that ,x It must be the missing smallest positive integer , as follows :
Replace the goal | x( The missing smallest positive integer ) |
[1, 2, 0] | 3 |
[1, -1, 3, 4] | 2 |
[6, 7, 8, 12] | 1 |
The time complexity of the algorithm is O(n), The space complexity is O(1), It fully meets the requirements of the topic . Now that the algorithm is determined , So the corresponding program is relatively simple , as follows :
package main
import "fmt"
func solution(a []int) int {
n := len(a)
for i := 0; i < n; i++ {
// Be careful : Here we're going to use for, instead of 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))
}
result :2
in summary : Algorithm 1 Sum algorithm 2 Can't pass the interview , Algorithm 3 Sum algorithm 4 You can go through an interview . among , Algorithm 3 It's rather winding , It's not easy to think of . By comparison , Algorithm 4 Intuitive and easy to understand , In the implementation of the program to pay attention to the inner layer to use for, instead of if.
overall ,B The company's interview requirements are still very high , I wish you all the best offer.
版权声明
本文为[osc_redits]所创,转载请带上原文链接,感谢
边栏推荐
- YGC troubleshooting, let me rise again!
- 攻防世界之web新手题
- PCIe 枚举过程
- python小工具:编码转换
- next.js实现服务端缓存
- Which is more worth starting with the difference between vivos7e and vivos7
- 抖音直播监控Api:随机推荐
- How does spotify drive data-driven decision making?
- print( 'Hello,NumPy!' )
- If you don't understand the gap with others, you will never become an architect! What's the difference between a monthly salary of 15K and a monthly salary of 65K?
猜你喜欢
随机推荐
python 循环区分(while循环和for循环)
Game optimization performance (11) - Zhihu
Japan PSE certification
Cloud alibabab notes come out, the whole network detailed explanation only this one hand is slow
413【毕设课设】基于51单片机无线zigbee无线智能家居光照温湿度传输监测系统
Installing MacOS 11 Big Sur in virtual machine
An error occurred while starting the kernel was successfully resolved
新的目标市场在哪里?锚定的产品是什么?| 十问2021中国企业服务
How can a technician take over a complex system?
Is software testing training class easy to find a job
比Python快20%,就问你兴不兴奋?
The difference between vivoy 73s and glory 30 Youth Edition
Function periodic table filter value selectedvalue
Mozi college SQL injection solution
[summary series] technical system of Internet server: high performance database index
Rust: command line parameter and environment variable operation
“1024”征文活动结果新鲜出炉!快来看看是否榜上有名?~~
渤海银行百万级罚单不断:李伏安却称治理完善,增速呈下滑趋势
2020-11-05
笔试面试题目:求缺失的最小正整数