Written interview questions: find the smallest positive integer missing

      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.