今天，我们来看一道有趣的腾讯三面的面试题，有一定难度和技巧。可以坦白地说，如果没有提前进行类似训练，那就不太可能现场做对这道题目，一起来看看：

腾讯题目：假设QQ号码的取值范围是(0, max_unsigned_int)，现有n个QQ号码，求出其中缺失的最小的QQ号码。要求时间复杂度为O(n)，空间复杂度为O(1).

熟悉LeetCode的朋友自然眼前一亮，这道题是咱们的老熟人啊，一起来看看LeetCode上的题目， 并以LeetCode题目为例，详细讲解具体的思路和解法。

LeetCode题目: 给定一个整数数组，请找出其中缺失的最小的正整数，要求时间复杂度为O(n)，空间复杂度为O(1)，输入输出的具体示例如下面表格所示：

我们先来分析一下:

• 假设a中的n个元素占满了1~n, 那么缺失的最小正整数就是n+1.
• 假设a中的n个元素没有完全占满1~n, 那么缺失的最小正整数必然是1~n之间的某个数。

综合可知：缺失的最小正整数必然在区间[1, n+1]中。这是一个非常重要的 结论。

基于该结论，我们来循序渐进地分析和讲解这道LeetCode题目，一起来看看吧。

一. *力暴**破解

*力暴**算法很简单，直接遍历区间[1, n+1]，然后判断元素是否在a中。此时，时间复杂度是O(n*n)，空间复杂度为O(1).

显然， 无法通过面试。

二. 哈希算法

从*力暴**破解的过程可知，这无非就是一个查找的问题，那么可以考虑用哈希表。具体如下：

把a数组用哈希表来记录，然后直接去遍历区间[1, n+1]，就可以判断元素是否在哈希表中。

此时，时间复杂度和空间复杂度都是O(n).

显然， 无法通过面试。

三. 巧妙标记

我们参考哈希算法，并在标记元素是否存在时做巧妙优化。

以a = [3, 4, 1, -1]为例，n = 4，过程如下：

可以看到，在记录元素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，刚好就是缺失的最小正整数。

四. 置换归位

我们再看看更加直观的想法。对于数组a的元素i，如果i在区间[1, n]中，可通过置换归位，把i放到a[i-1]处，如下：

置换后，再次遍历a, 如果a[x-1]和x不相等，那么，x肯定就是缺失的最小正整数，如下：

该算法的时间复杂度是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，刚好就是缺失的最小正整数。

今天先聊这么多，咱们明天见。愿大家提前做准备，秒杀算法题，面试要顺利哦。

来源：https://mp.weixin.qq.com/s/kAa2QSoGluSpq4B_7jFfmA