# Written interview questions: find the smallest positive integer missing

2020-11-08 10:30:26

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.